洛谷P4390 Mokia CDQ分治

时间：2021-04-11 15:21:49

喜闻乐见的CDQ分治被我搞的又WA又T.....

大致思路是这样的：把询问用二维前缀和的思想拆成4个子询问。然后施CDQ大法即可。

我却灵光一闪：树状数组是可以求区间和的，那么我们只拆成两个子询问不就行了？在统计的时候统计一个差值即可。

然后一交，自信40...

那么果然还是拆成4个吧...T了，60分。

然后放弃那个朴素的sort版CDQ，采用了归并，就A了。

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 const int N = ,M = ;

 inline int read()

 {

     int ans=;char ch=getchar();

     while(ch<''||ch>'') ch=getchar();

     while(ch>=''&&ch<='') ans=(ans<<)+(ans<<)+ch-'',ch=getchar();

     return ans;

 }

 struct Node

 {

     int x,y,k,type,t;

 }node[N],temp[N];int tot;

 int ask[],cnt,n;

 inline bool cmp_x(Node a,Node b)

 {

     if(a.x!=b.x)return a.x<b.x;

     return a.type<b.type;

 }

 inline bool cmp_t(Node a,Node b)

 {

     if(a.t!=b.t)return a.t<b.t;

     return a.type<b.type;

 }

 int ta[M];

 inline int lowbit(int i) {return i&(-i);}

 inline void add(int x,int a)

 {

     if(x<=) return;

     for(int i=x;i<=n;i+=lowbit(i)) ta[i]+=a;

     return;

 }

 inline int getsum(int x)

 {

     if(x<=) return ; int ans=;

     for(int i=x;i>;i-=lowbit(i)) ans+=ta[i];

     return ans;

 }

 void CDQ(int l,int r)

 {

     if(l==r)return;

     int mid=(l+r)>>;

     CDQ(l,mid);CDQ(mid+,r);

     int i=l,j=mid+,t=;

     while(j<=r||i<=mid)

     {

         if(j>r||(i<=mid&&node[i].x<=node[j].x))

         {

             if(node[i].type==) add(node[i].y,node[i].k);

             temp[++t]=node[i++];

         }

         else

         {

             if(node[j].type>) node[j].k+=getsum(node[j].y);

             temp[++t]=node[j++];

         }

     }

     for(j=l;j<i;j++)

     {

         if(node[j].type==)add(node[j].y,-node[j].k);

     }

     t=;

     for(i=l;i<=r;i++) node[i]=temp[++t];

     return;

 }

 int main()

 {

     n=read();n=read();

     int flag,x,y,xx,yy,k,time=;

     flag=read();

     while(flag!=)

     {

         time++;

         if(flag==)

         {

             x=read();y=read();k=read();

             node[++tot].x=x;

             node[tot].y=y;

             node[tot].k=k;

             node[tot].t=time;

             node[tot].type=;

         }

         else

         {

             x=read();y=read();xx=read();yy=read();

             x--;y--;

             node[++tot].x=xx;

             node[tot].y=yy;

             node[tot].t=time;

             node[tot].type=;

             ask[++cnt]=tot;

             node[++tot].x=x;

             node[tot].y=y;

             node[tot].t=time;

             node[tot].type=;

             node[++tot].x=x;

             node[tot].y=yy;

             node[tot].t=time;

             node[tot].type=;

             node[++tot].x=xx;

             node[tot].y=y;

             node[tot].t=time;

             node[tot].type=;

         }

         flag=read();

     }

     CDQ(,tot);

     sort(node+,node+tot+,cmp_t);

     for(int i=;i<=cnt;i++)

     {

         int p=ask[i];

         int ans=node[p].k+node[p+].k-node[p+].k-node[p+].k;

         printf("%d\n",ans);

     }

     return ;

 }

AC代码：

相关文章