A Simple Problem with Integers

描述

题目大意有n个数，m个操作 操作1: 对区间[l,r]给每一个满足[A-l]%k==0的数+c 操作2: 求一个点a的值

思路

线段树维护，因为k很小，所以可以对每一个节点维护k个flag每一个flag表示到该区间左端点满足是k的整数倍的节点要加多少（类似于剩余系）。 第一次打这种类型的线段树，调了2h。。。。 真弱啊！ 而且没有发现多组数据。

代码

#include <iostream> #include <cstdio> #include <cstring> #define ROOT 1,1,n #define LSON root<<1,l,mid #define RSON root<<1|1,mid+1,r using namespace std; const int maxn=50000+2; int m,n,a[maxn]; bool used[12]; struct node { int data,flag[11]; }T[maxn*4]; void build(int root,int l,int r) { if(l==r) { T[root].data=a[l]; return; } else { int mid=(l+r)>>1; build(LSON); build(RSON); } } void modify(int root,int l,int r,int L,int R,int k,int c) { if(l==L && r==R) { if(l==r) T[root].data+=c; else T[root].flag[k]+=c; return; } int mid=(l+r)>>1; if(R<=mid) modify(LSON,L,R,k,c); else if(L>mid) modify(RSON,L,R,k,c); else { modify(LSON,L,mid,k,c); int new_l=L+((mid-L)/k)*k+k; if(new_l<=R) modify(RSON,new_l,R,k,c); } } int query(int root,int l,int r,int k,int sumflag) { if(l==r) return T[root].data+sumflag; else { int mid=(l+r)>>1; int tmp=0; // cout<<l<<"->"<<r<<':'<<endl; for(int i=1; i<=10; i++) { // cout<<(k-l)%i<<' '<<T[root].flag[i]<<endl; if((k-l)%i==0) tmp+=T[root].flag[i]; } // cout<<'('<<tmp<<')'<<endl; if(k<=mid) return query(LSON,k,sumflag+tmp); else return query(RSON,k,sumflag+tmp); } } int main() { freopen("test.in","r",stdin); freopen("test1.out","w",stdout); while(scanf("%d",&n)==1) { for(int i=1; i<=n; i++) { scanf("%d",&a[i]); } memset(T,0,sizeof(T)); build(ROOT); scanf("%d",&m); while(m--) { int opt; scanf("%d",&opt); if(opt==1) { int l,r,k,c; scanf("%d %d %d %d",&l,&r,&k,&c); modify(ROOT,l,r,k,c); } else { int location; scanf("%d",&location); printf("%d\n",query(ROOT,location,0)); // puts("#####################"); } } } return 0; }