BZOJ 1176([Balkan2007]Mokia-CDQ分治-分治询问)-白红宇

BZOJ 1176([Balkan2007]Mokia-CDQ分治-分治询问)

阅读量：7195 次

发布时间：2019-06-29

本文共 2332 字，大约阅读时间需要 7 分钟。

1176: [Balkan2007]Mokia

Time Limit: 30 Sec

Memory Limit: 162 MB

Submit: 185

Solved: 94

[ ][ ]

Description

维护一个W*W的矩阵，每次操作可以增加某格子的权值，或询问某子矩阵的总权值。修改操作数M<=160000，询问数Q<=10000，W<=2000000。

Input

Output

Sample Input

0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3

Sample Output

3
5

HINT

Input file Output file Meaning

0 4 Table size is , filled with zeroes.

1 2 3 3 Add 3 customers at (2, 3).

2 1 1 3 3 Query sum of rectangle , .

3 Answer.

1 2 2 2 Add 2 customers at (2, 2).

2 2 2 3 4 Query sum of rectangle , .

5 Answer

3 Exit your program.

裸CDQ...1A

注意几个关键部分的写法

步骤：

1.读入询问，按x排序

2.将[L,R]中的数分为前部分操作，后部分操作（各部分仍保持X升序）

3.将前面对后面的影响记录ans

4.复原影响

5.递归[L,M],[M+1,R]

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;#define For(i,n) for(int i=1;i<=n;i++)#define Rep(i,n) for(int i=0;i
              
               =0;i--)#define MEM(a) memset(a,0,sizeof(a))#define MEMI(a) memset(a,127,sizeof(a))#define MEMi(a) memset(a,128,sizeof(a))#define INF (2139062143)#define F (1000000009)#define MAXM (640000+10)#define MAXQ (10000+10)#define MAXN (2000000+10) typedef long long ll;int n,m,q;ll ans[MAXQ];struct comm{ int no,x,y,v,q,type; comm():no(0),x(0),y(0),v(0),q(0),type(0){} comm(int _no,int _x,int _y,int _v,int _q,int _type):no(_no),x(_x),y(_y),v(_v),q(_q),type(_type){} friend bool operator<(comm a,comm b){return a.x
               
                >1; int s1=l-1,s2=m; Fork(i,l,r) tmp[ask[i].no<=m?++s1:++s2]= ask[i]; memcpy(ask+l,tmp+l,sizeof(comm)*(r-l+1)); int now=l; Fork(i,m+1,r) //遍历询问 { if (ask[i].type==2) { while (ask[now].x<=ask[i].x&&now<=m) { if (ask[now].type==1) T.add(ask[now].y,ask[now].v); now++; } ans[ask[i].q]+=ask[i].v*T.qur(ask[i].y); } } now--; while (l<=now) {if (ask[now].type==1) T.add(ask[now].y,-ask[now].v);now--;} solve(l,m),solve(m+1,r);}bool work(){ scanf("%d",&n); int type,no=0,x,y,x1,y1,x2,y2,v,q=0; memset(ans,0,sizeof(ans));T.clear(); while (scanf("%d",&type)) { if (type==0||type==3) break; else if (type==1) { scanf("%d%d%d",&x,&y,&v); no++;ask[no]=comm(no,x,y,v,0,1); } else if (type==2) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2);q++; no++;ask[no]=comm(no,x1-1,y1-1,1,q,2); no++;ask[no]=comm(no,x2,y2,1,q,2); no++;ask[no]=comm(no,x1-1,y2,-1,q,2); no++;ask[no]=comm(no,x2,y1-1,-1,q,2); } } sort(ask+1,ask+1+no); solve(1,no); For(i,q) cout<
                
                 <