CDQ分治論文例題。。 論文戳我
#include <cstdio>#include <cstring>#include <algorithm>#include <cstring>#include <cmath>#define MAXN 200005#define N 2000005#define LL long long#define INF 1000000005#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))using namespace std;const double eps = 1e-8;inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}int n,m,s,c[N],ans[MAXN];inline int lowbit(int i){return i&(-i);}struct t{int opt,to,add,x,y,f,pos;}p[MAXN],tmp[MAXN];void add(int x,int v){ for(int i=x;i<=n;i+=lowbit(i)) c[i]+=v;}int query(int x){ int t=0; for(int i=x;i;i-=lowbit(i)) t+=c[i]; return t;}void addquery(int x1,int y1,int x2,int y2){ ans[0]++; p[++m].pos=m,p[m].to=ans[0],p[m].x=x1-1,p[m].y=y1-1,p[m].opt=0,p[m].f=1; p[++m].pos=m,p[m].to=ans[0],p[m].x=x2,p[m].y=y2,p[m].opt=0,p[m].f=1; p[++m].pos=m,p[m].to=ans[0],p[m].x=x1-1,p[m].y=y2,p[m].opt=0,p[m].f=-1; p[++m].pos=m,p[m].to=ans[0],p[m].x=x2,p[m].y=y1-1,p[m].opt=0,p[m].f=-1;}void solve(int l,int r){ if(l==r) return; int mid=(l+r)>>1,l1=l,l2=mid+1; for(int i=l;i<=r;i++) { if(p[i].pos<=mid&&p[i].opt) add(p[i].y,p[i].add); if(p[i].pos>=mid+1&&(!p[i].opt)) ans[p[i].to]+=p[i].f*query(p[i].y); } for(int i=l;i<=r;i++) if(p[i].pos<=mid&&p[i].opt) add(p[i].y,-p[i].add); for(int i=l;i<=r;i++) if(p[i].pos<=mid) tmp[l1++]=p[i]; else tmp[l2++]=p[i]; for(int i=l;i<=r;i++) p[i]=tmp[i]; solve(l,mid),solve(mid+1,r);}bool cmp(t a,t b){ if(a.x==b.x&&a.y==b.y)return a.opt>b.opt; if(a.x==b.x) return a.y<b.y; else return a.x<b.x;}int main(){ s=read(),n=read(); while(1) { int t=read(); if(t==1) p[++m].pos=m,p[m].x=read(),p[m].y=read(),p[m].opt=1,p[m].add=read(); else if(t==2) { int x1=read(),y1=read(),x2=read(),y2=read(); addquery(x1,y1,x2,y2); } else break; } sort(p+1,p+1+m,cmp); solve(1,m); for(int i=1;i<=ans[0];i++)新聞熱點
疑難解答
