_H17_ @ 2024-11-16 10:32:34
#include<bits/stdc++.h>
#define int long long
#define ALL(x) x.begin(),x.end()
using namespace std;
constexpr int N=1e6+1;
struct ChthollyTreeNode{
int l,r;
mutable int val;
ChthollyTreeNode(int l=0,int r=0,int val=0):l(l),r(r),val(val){}
friend bool operator<(ChthollyTreeNode a,ChthollyTreeNode b){
return a.l<b.l;
}
};
set<ChthollyTreeNode>odt;
int n,q,a[N];
void build(){
int lst=1;
for(int i=2;i<=n;i++)
if(a[i]!=a[lst]){
odt.insert(ChthollyTreeNode(lst,i-1,a[lst]));
lst=i;
}
odt.insert(ChthollyTreeNode(lst,n,a[n]));
return;
}
set<ChthollyTreeNode>::iterator split(int x){//split[l,x-1],[x,r]
set<ChthollyTreeNode>::iterator id=odt.lower_bound(ChthollyTreeNode(x,0,0));
if(id==odt.end())
return id;
if((id->l)==x)
return id;
ChthollyTreeNode old=(*(--id));
odt.erase(id);
odt.insert(ChthollyTreeNode(old.l,x-1,old.val));
return odt.insert(ChthollyTreeNode(x,old.r,old.val)).first;
}
void assign(int l,int r,int val){
set<ChthollyTreeNode>::iterator it2=split(r+1),it1=split(l);
odt.erase(it1,it2),odt.insert(ChthollyTreeNode(l,r,val));
return;
}
void add(int l,int r,int val){
for(set<ChthollyTreeNode>::iterator it2=split(r+1),it1=split(l);it1!=it2;it1++)
(it1->val)+=val;
return;
}
int query(int l,int r){
int ret=-9e18;
for(set<ChthollyTreeNode>::iterator it2=split(r+1),it1=split(l);it1!=it2;it1++)
ret=max(ret,it1->val);
return ret;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(nullptr);
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>a[i];
build();
for(int op,l,r,x;q;--q){
cin>>op>>l>>r;
if(op==1){
cin>>x;
assign(l,r,x);
}
else if(op==2){
cin>>x;
add(l,r,x);
}
else
cout<<query(l,r)<<'\n';
}
return 0;
}只调 WA 部分。
by Lyw_Cyq_01 @ 2024-11-16 10:49:56
@H17 貌似要开 long long？（珂朵莉树哪来的 build()，代码看的不是很懂）
by _H17_ @ 2024-11-16 10:50:37
@Lyw_Cyq_01首先上面开了，其次 build 是建珂朵莉树
by Lyw_Cyq_01 @ 2024-11-16 10:51:00
@H17 总之要先开 long long
by _H17_ @ 2024-11-16 10:51:36
就是出使的颜色段扔进去
by _H17_ @ 2024-11-16 10:51:55
@Lyw_Cyq_01我开了！你没看见？
by _H17_ @ 2024-11-16 10:53:07
@Lyw_Cyq_01最上面的define int long long
by Lyw_Cyq_01 @ 2024-11-16 10:54:42
@H17 这玩意数据稍大一点就会 T 飞，所以有没有可能看似 WA，实则 TLE
by _H17_ @ 2024-11-16 10:56:02
@Lyw_Cyq_01洛谷会优先跑完，在判断 WA，也就是如果先 WA 了在 TLE 会显示 TLE，所以我这个只是普通的 WA.
而且要审题，我只让调 WA 的部分嘿嘿。
by Lyw_Cyq_01 @ 2024-11-16 11:01:47
@H17 我刚刚自己手打了一遍，你看看：
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
ll n, q;
struct node {
ll l, r; mutable ll v;
node (ll L, ll R, ll V) {
l = L, r = R, v = V;
}
friend bool operator < (node x, node y) {
return x.l < y.l;
}
}; set<node> odt;
set<node>::iterator split(ll x) {
set<node>::iterator it = odt.lower_bound(node(x, 0, 0));
if (it != odt.end() && it -> l == x) return it; it --;
ll l = it -> l, r = it -> r, v = it -> v;
odt.erase(it); odt.insert(node(l, x - 1, v));
return odt.insert(node(x, r, v)).first;
}
void assign(ll l, ll r, ll v) {
set<node>::iterator itr = split(r + 1), itl = split(l);
odt.erase(itl, itr); odt.insert(node(l, r, v));
}
void modify(ll l, ll r, ll V) {
for (set<node>::iterator itr = split(r + 1), itl = split(l); itl != itr; itl ++) {
itl -> v += V;
}
}
ll query(ll l, ll r) {
ll res = LLONG_MIN;
for (set<node>::iterator itr = split(r + 1), itl = split(l); itl != itr; itl ++) {
res = max(res, (itl -> v));
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> q;
for (ll i = 1; i <= n; i++) {
ll x; cin >> x; odt.insert(node(i, i, x));
}
while (q--) {
ll op, l, r, x;
cin >> op >> l >> r;
if (op == 1) {
cin >> x; assign(l, r, x);
} else if (op == 2) {
cin >> x; modify(l, r, x);
} else {
cout << query(l, r) << endl;
}
}
}#5 #6 T，其它 AC，你参考下
by Lyw_Cyq_01 @ 2024-11-16 11:04:36
@H17 可能跟你的马蜂习惯不一样，你可以参考下，我总感觉问题出在 split() 和 build() 上，并且珂朵莉树一般是默认不写 build() 的，当然你要能写对那我也没意见，所以问题大概率出在 split() 上。