为啥这个CDQ分治会WA啊?
查看原帖
为啥这个CDQ分治会WA啊?
200044
JS_TZ_ZHR楼主2021/4/17 21:27
#include<bits/stdc++.h>
#define N 4000005
#define int long long
#define ll long long
#define lowbit(k) k&(-k)
using namespace std;
int opt,w,a,b,c,d,tree[N],cnt;
struct node{
	int opt,t,x,y,val;
}x[N];
void add(int p,int k) {
	while(p<=w) {
		tree[p]+=k;
		p+=lowbit(p);
	}
	return;
}
int query(int p) {
	int res=0;
	while(p) {
		res+=tree[p];
		p-=lowbit(p);
	}
	return res;
}
bool cmp1(node u,node v){
	if(u.x!=v.x)return u.x<v.x;
	return u.y<v.y;
}
bool cmp2(node u,node v){
	return u.t<v.t;
}
void solve(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1;
	solve(l,mid),solve(mid+1,r);
	sort(x+l,x+mid+1,cmp1),sort(x+mid+1,x+r+1,cmp1);
	int j=l;
	for(int i=mid+1;i<=r;i++){
		while(j<=mid&&x[j].x<=x[i].x)add(x[j].y,x[j].val*x[j].opt),j++;
		if(!x[i].opt)x[i].val+=query(x[i].y);
	}
	for(int i=l;i<j;i++)add(x[i].y,-x[i].val*x[i].opt);
}
signed main() {
	while(1){
		cin>>opt;
		if(opt==0){
			cin>>w;
			w++;
		}
		else if(opt==1){
			cin>>a>>b>>c;
			a++,b++;
			x[++cnt]=(node){
				1,cnt,a,b,c
			};
		}
		else if(opt==2){
			cin>>a>>b>>c>>d;
			c++,d++;
			x[++cnt]=(node){
				0,cnt,a,b,0
			};
			x[++cnt]=(node){
				0,cnt,c,d,0
			};
			x[++cnt]=(node){
				0,cnt,a,d,0
			};
			x[++cnt]=(node){
				0,cnt,c,b,0
			};
		}
		else break;
	}
	solve(1,cnt);
	sort(x+1,x+cnt+1,cmp2);
	x[0].opt=1;
	for(int i=1;i<=cnt;i++)
		if(x[i].opt==0&&x[i-1].opt==1)cout<<x[i].val+x[i+1].val-x[i+2].val-x[i+3].val<<endl;
}
2021/4/17 21:27
加载中...