长春赛区2012 A Simple Problem with Integers 1001题

题目:http://acm.hdu.edu.cn/showproblem.php?pid=4267

线段树，注意k很小，更新优化。

//STATUS:C++_AC_218MS_3904KB  #include<stdio.h>#include<stdlib.h>#include<string.h>#include<vector>#include<queue>#include<math.h>#include<map>using namespace std;const int MAX=50010,INF=200000000;const double esp=1e-6;struct info{int k,mod,c;info *next;}*seg[MAX<<2];void update(int l,int r,int rt);void query(int l,int r,int rt);int n,num[MAX],a,b,k,c,ans;int main(){//freopen("in.txt","r",stdin);int i,op,q;while(~scanf("%d",&n)){memset(seg,0,sizeof(seg));for(i=1;i<=n;i++)scanf("%d",&num[i]);scanf("%d",&q);while(q--){scanf("%d",&op);if(op==1){scanf("%d%d%d%d",&a,&b,&k,&c);update(1,n,1);}else {ans=0;scanf("%d",&a);query(1,n,1);printf("%d\n",num[a]+ans);}}}return 0;}void update(int l,int r,int rt){if(a<=l && r<=b){int mod=k-(l-a)%k;    //更新优化        if(mod>=k)mod-=k;        for(info* q=seg[rt];q!=NULL;q=q->next)        {            if(q->k==k && q->mod==mod){                q->c+=c;                return;            }        }info* p=new info();        p->k=k,p->c=c,p->mod=mod;        p->next=seg[rt];        seg[rt]=p;return;}int mid=(l+r)>>1;if(a<=mid)update(l,mid,rt<<1);if(b>mid)update(mid+1,r,rt<<1|1);}void query(int l,int r,int rt){info *p=NULL;    for(p=seg[rt];p!=NULL;p=p->next){        if((a-l)%p->k==p->mod)ans+=p->c;    }if(l==r)return;int mid=(l+r)>>1;if(a<=mid)query(l,mid,rt<<1);else query(mid+1,r,rt<<1|1);}