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

长春赛区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);
}