首页 > 代码库 > BZOJ1176: [Balkan2007]Mokia

BZOJ1176: [Balkan2007]Mokia

2024-07-29 05:40:35   216人阅读

1176: [Balkan2007]Mokia

Time Limit: 30 Sec  Memory Limit: 162 MB
Submit: 436  Solved: 207
[Submit][Status]

Description

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

Input

第一行两个整数,S,W;其中S为矩阵初始值;W为矩阵大小

接下来每行为一下三种输入之一(不包含引号):

"1 x y a"

"2 x1 y1 x2 y2"

"3"

输入1:你需要把(x,y)(第x行第y列)的格子权值增加a

输入2:你需要求出以左上角为(x1,y1),右下角为(x2,y2)的矩阵内所有格子的权值和,并输出

输入3:表示输入结束

Output

对于每个输入2,输出一行,即输入2的答案

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

 

保证答案不会超过int范围

 

Source

题解：

居然拖了一星期没写。。。

在线不能做是因为空间开不下，只允许我们开一个一维的树状数组。

考虑CDQ分治：solve(l,r)

考虑(l,mid)中的修改对(mid+1,r)的查询操作的影响

首先我们可以把一个矩形区域分成sum(x2,y2)-sum(x2,y1-1)-sum(x1-1,y2)+sum(x1-1,y1-1)

sum表前缀和

然后我们可以按x排序，然后让pos<=mid的查询在 y 坐标生效，让pos>mid的查询ans+= y 坐标的前缀和

想一想

1）pos>mid的修改我们没有考虑

2）pos<=mid但修改的x>查询的x的我们没有也不需要提前更新

3）pos<=mid并且修改的x<=查询的x，修改的y>查询的y，我们在用树状数组求前缀和的时候已经忽略了

综上，该算法不重不漏得考虑了（l，mid）的修改对（mid+1，r）的查询操作的影响

所以这样求出来就是正确的

代码：

 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 2000000+1000014 #define maxm 500+10015 #define eps 1e-1016 #define ll int17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26     int x=0,f=1;char ch=getchar();27     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29     return x*f;30 }31 struct rec{int x,y,c,pos,id;ll z;}a[maxn];32 int n,m,t,tot;33 ll s[maxn],c[maxn];34 inline bool cmp1(rec a,rec b){return a.x<b.x||(a.x==b.x&&a.pos<b.pos);}35 inline bool cmp2(rec a,rec b){return a.pos<b.pos;}36 inline void add(int x,ll y)37 {38     for(;x<=m;x+=x&(-x))s[x]+=y;39 }40 inline ll sum(int x)41 {42     ll t=0;43     for(;x;x-=x&(-x))t+=s[x];44     return t;45 }46 void solve(int l,int r)47 {48     int mid=(l+r)>>1;49     if(l==r)return;50     sort(a+l,a+r+1,cmp1);51     for2(i,l,r)52      {53          if(a[i].pos<=mid&&a[i].c==1)add(a[i].y,a[i].z);54          if(a[i].pos>mid&&a[i].c!=1)c[a[i].id]+=a[i].z*sum(a[i].y); 55      }56     for2(i,l,r)57         if(a[i].pos<=mid&&a[i].c==1)add(a[i].y,-a[i].z);58     sort(a+l,a+r+1,cmp2);59     solve(l,mid);solve(mid+1,r);60 }61 int main()62 {63     freopen("input.txt","r",stdin);64     freopen("output.txt","w",stdout);65     t=read();m=read();66     while(1)67     {68         a[++n].c=read();69         if(a[n].c==3){n--;break;}70         if(a[n].c==1)a[n].x=read(),a[n].y=read(),a[n].z=read();71         else 72          {73              int x1=read(),y1=read(),x2=read(),y2=read();74             c[++tot]=(x2-x1+1)*(y2-y1+1)*t;75             a[n].x=x2;a[n].y=y2;a[n].z=1;76             a[++n].x=x1-1;a[n].y=y2;a[n].z=-1;77             a[++n].x=x2;a[n].y=y1-1;a[n].z=-1;78             a[++n].x=x1-1;a[n].y=y1-1;a[n].z=1;79             a[n].id=a[n-1].id=a[n-2].id=a[n-3].id=tot;80          }81     }82     for1(i,n)a[i].pos=i;83     solve(1,n);84     for1(i,tot)printf("%d\n",c[i]);        85     return 0; 86 }
View Code

代码倒数了T_T

BZOJ1176: [Balkan2007]Mokia


联系
我们