赞
踩
给定长度为n的序列a1,a2...an,则sum[i]=a1+...+ai=sum[i-1]+a[i]
- for(i=1;i<=n;i++)
- {
- cin>>a[i];
- a[i]+=a[i-1];
- }
差分:每个元素与前一个元素的差值
如 A:1 2 3 4 5
则差分为 1 1 1 1 1
若将A[1]+1, A : 1 3 3 4 5
则 1 2 0 1 1 只会改变自己和后一个数
m次操作,每次将区间[L,R]的值加p,最后询问区间[L,R]元素之和。
solution:用一个数组b记录对每一个前缀和总的修改(也可以就在a上操作)。则每次b[L]+=p,b[R]-=p(代表从L及以后的每个元素都要+p,而R及其以后的每个元素-p(所以R之后的元素相当于没操作))
- for(i=1; i<=m; i++)
- {
- int L,R;
- cin>>L>>R>>p;
- b[L]+=p;
- b[R+1]-=p;
- }
-
- int add=0;
- for(i=1; i<=n; i++)
- {
- add+=b[i];
- a[i]+=a[i-1]+add;
- }
-
- //若直接用a表示则为:
- for(i=1; i<=m; i++)
- {
- int L,R;
- cin>>L>>R>>p;
- a[L]+=p;
- a[R+1]-=p;
- }
-
- int add=0;
- for(i=1; i<=n; i++)
- {
- add+=a[i];
- a[i]+=a[i-1];
- }
要求[L,R]的和即a[R]-a[L-1],注意下标从0开始时要特判L=0
这时操作对象从一维数组变为二维数组,sum[i][j]表示以a[0][0]为左上角,a[i][j]为右下角的矩阵的和,则可推出
sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i][j] +a[i][j]//容斥
- for(i, 1, n)
- for(j, 1, n)
- {
- scanf("%d", &a[i][j]);
- a[i][j] +=a[i-1][j] + a[i][j-1] - a[i-1][j-1];
- }
m次操作,每次将以[x1,y1]为左上角,[x2,y2]为右上角的矩阵的值加p,最后询问区间[L,R]元素之和。
同样地,我们记录下每次操作对区间和的影响。b[i][j]表示以[0][0]为左上角的矩阵,若包含a[i][j]则要+p,所以有4处影响:
b[x1][y1]+=p;
b[x1][y2=1]-=p;(右边区域+、-各一次,抵消使得1号区域不收影响);
b[x2+1][y1]-=p;(下边区域+、-各一次,抵消使得2号区域不收影响);
b[x2+1][y2+1]+=p;(右下边区域+、-各两次,抵消使得3号区域不收影响);
- for(i, 1, m)
- {
- int x1, y1, x2, y2, p;
- scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &p);
- a[x1][y1] += p;
- a[x1][y2+1] -= p;
- a[x2+1][y1] -= p;
- a[x2+1][y2+1] += p;
- }
-
- //注意这样算的是每一个元素更新之后的值,不是和!要求和的话不仅要加a[i][j]还得加上覆盖矩阵的每一个未更新a[i][j],即累加add
- for(i, 1, n)
- for(j, 1, n)
- a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
则查询以[x1,y1]为左上角,[x2,y2]为右上角的矩阵的值的和:
ans=a[x2][y2]-a[x2,y2-1]-a[x2-1][y2]+a[x1][y1]
theme:给定一个n*n螺旋矩阵,现从螺旋矩阵中选出m个位置,每个位置的价值由它的元素值的每个数位之和表示,其余位置的元素全部置为0,q次询问,每次询问子矩阵价值。1<=n<=1e6,m,q<=1e5
solution:首先要根据螺旋矩阵的性质推出给定x,y,矩阵中(x,y)的元素值。之后问题转化为求二维矩阵的前缀和。n范围很大,所以借助树状数组辅助。
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N=(int)1e6+10;
-
- ll bit[N],ans[N];
- void Init(int n)
- {
- for(int i=1;i<=n;++i)
- bit[i]=ans[i]=0;
- }
- /******************树状数组**************/
- int lowbit(int x)
- {
- return x&(-x);
- }
-
- void add(int i,ll t)
- {
- while(i<=N)
- {
- bit[i]+=t;
- i+=lowbit(i);
- }
- }
- ll sum(int i)
- {
- ll sum=0;
- while(i)
- {
- sum+=bit[i];
- i-=lowbit(i);
- }
- return sum;
- }
- /******************矩阵**************/
- struct node
- {
- int f;//标志是矩阵原数0插入还是求区间和时的ans+/-,1
- int x,y,ans_id;
- ll val;//标志求前缀和时是减掉还是加上该矩阵
- friend bool operator<(node a,node b)//y,x,f
- {
- if(a.y==b.y)
- {
- if(a.x==b.x)
- return a.f<b.f;
- return a.x<b.x;
- }
- return a.y<b.y;
- }
- }p[N];
- ll re_val(ll x)
- {
- ll sum=0;
- while(x>0)
- {
- sum+=x%10;
- x/=10;
- }
- return sum;
- }
- /************螺旋矩阵*************/
- long long index(long long y,long long x,long long n)
- {
- long long mid=(n+1)/2;
- long long p=max(abs(x-mid),abs(y-mid));
- long long ans=n*n-(1+p)*p*4;
- long long sx=mid+p,sy=mid+p;
- if(x==sx&&y==sy)
- return ans;
- else
- {
- if(y==sy||x==sx-2*p)
- return ans+abs(x-sx)+abs(y-sy);
- else
- return ans+8*p-abs(x-sx)-abs(y-sy);
- }
- }
- /*************二位前缀和***************/
- void solve(int n)
- {
- for(int i=1;i<=n;++i)
- {
- if(p[i].f) ans[p[i].ans_id]+=sum(p[i].x)*p[i].val;
- else add(p[i].x,p[i].val);
- }
- }
-
- int main()
- {
- int T;
- scanf("%d",&T);
- while(T--)
- {
- int n,m,ask;
- scanf("%d%d%d",&n,&m,&ask);
- Init(N-3);
- int cnt=0;
- for(int i=1;i<=m;++i)
- {
- int x,y;
- scanf("%d%d",&x,&y);
- p[++cnt]={0,x,y,-1,re_val(index(x,y,n))};
- }
- for(int i=1;i<=ask;++i)
- {
- int xl,yl,xr,yr;
- scanf("%d%d%d%d",&xl,&yl,&xr,&yr);
- p[++cnt]={1,xl-1,yl-1,i,1};
- p[++cnt]={1,xl-1,yr,i,-1};
- p[++cnt]={1,xr,yl-1,i,-1};
- p[++cnt]={1,xr,yr,i,1};
- }
- sort(p+1,p+1+cnt);
- solve(cnt);
- for(int i=1;i<=ask;++i)
- printf("%lld\n",ans[i]);
- }
- return 0;
- }
theme:三种操作:
(1):1 x:表示从位置x开始一直到n,每个数+1
(2): 2 x :表示从x到n,依次增加1 2 3 4、、、
(3):3 x:表示从x到n,依次增加1 4 9 16、、、
- #include<bits/stdc++.h>
- using namespace std;
- #define far(i,t,n) for(int i=t;i<n;++i)
- typedef long long ll;
- typedef unsigned long long ull;
- using namespace std;
-
- int a[100010],b[100010],c[100010];
- int mod=1e9+7;
-
- void pre(int p[],int n)
- {
- p[0]%=mod;
- far(i,1,n)
- p[i]=(p[i]+p[i-1]%mod)%mod;
- }
-
- int main()
- {
- int t;
- cin>>t;
- while(t--)
- {
- int n,m;
- scanf("%d%d",&n,&m);
- memset(a,0,sizeof(a));
- memset(b,0,sizeof(b));
- memset(c,0,sizeof(c));
- far(i,0,m)
- {
- int op,pos;
- scanf("%d%d",&op,&pos);
- --pos;
- if(op==1)
- a[pos]++;
- else if(op==2)
- b[pos]++;
- else
- c[pos]++,c[pos+1]++;
- }
-
- pre(a,n);
- pre(b,n);pre(b,n);
- pre(c,n);pre(c,n);pre(c,n);
-
- far(i,0,n)
- printf("%d ",(a[i]+b[i]+c[i])%mod);
- printf("\n");
- }
- }
差分套差分:
theme:两种操作: 1 l r:表示将区间[l,r]的数+1,2 l r :表示将编号[l,r]的操作再执行一遍(保证l,r为已出现的编号)。开始时n个数为0,问最终每个数为多少?
solution:最终我们要算出每个1操作执行了多少次,再对这些区间进行差分,一遍前缀和可得到结果。而对操作次数进行差分的时候,应该逆序进行,从后往前,进行差分,两个差分同步进行。
- #include<bits/stdc++.h>
- using namespace std;
- #define far(i,t,n) for(int i=t;i<n;++i)
- typedef long long ll;
- typedef unsigned long long ull;
- using namespace std;
-
- map<int,int>m;
- map<int,int>::iterator it;
- priority_queue<int>q;
-
- int main()
- {
- int n;
- cin>>n;
- far(i,0,n)
- {
- int x;
- scanf("%d",&x);
- m[x]++;
- }
- int ans=0;
- for(it=m.begin();it!=m.end();++it)
- q.push(it->second);
-
- while(q.size()>=3)
- {
- ++ans;
- int x1=q.top()-1;
- q.pop();
- int x2=q.top()-1;
- q.pop();
- int x3=q.top()-1;
- q.pop();
- if(x1)q.push(x1);
- if(x2)q.push(x2);
- if(x3)q.push(x3);
- }
- cout<<ans<<"\n";
- }
- /*
- 13
- 1 2 3 3 4 4 4 4 5 5 5 5 5
- */
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。