hdu 4031 2011成都赛区网络赛A题 线段树 ***

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
#define MOD 1000000007
const int INF=0x3f3f3f3f;
const double eps=1e-;
#define cl(a) memset(a,0,sizeof(a))
#define ts printf("*****\n");
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root 1,n,1
#define mid ((l+r)>>1)
const int MAXN=;
int n,m,t,Min;
int sum[MAXN<<],col[MAXN<<];
void pushup(int rt){
sum[rt]=sum[rt<<]+sum[rt<<|];
}
void pushdown(int rt,int m)
{
if(col[rt]!=)
{
sum[rt<<]+=(m-(m>>))*col[rt]; //位运算一定要带括号
sum[rt<<|]+=(m>>)*col[rt];
col[rt<<]+=col[rt];
col[rt<<|]+=col[rt];
col[rt]=;
}
}
void build(int l,int r,int rt){
col[rt]=;
sum[rt]=;
if(l==r) return;
build(lson);
build(rson);
pushup(rt);
}
void update(int L,int R,int val,int l,int r,int rt)
{
if(l>=L&&r<=R)
{
col[rt]+=val;
sum[rt]+=(r-l+)*val;
return;
}
pushdown(rt,r-l+);
if(L<=mid) update(L,R,val,lson);
if(R>mid) update(L,R,val,rson);
pushup(rt);
}
int query(int pos,int l,int r,int rt)
{
if(l==r)
{
return sum[rt];
}
pushdown(rt,r-l+);
if(pos<=mid) return query(pos,lson);
else return query(pos,rson);
}
struct Node
{
int l,r;
Node(){}
Node(int ll,int rr)
{
l=ll,r=rr;
}
}node[MAXN];
int cnt[MAXN],last[MAXN];
int main()
{
int i,j,k;
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int u,v,tt,x,q,l;
scanf("%d",&tt);
int ca=;
while(tt--)
{
scanf("%d%d%d",&n,&q,&t);
build(root);
cl(last);
cl(cnt);
int tot=;
printf("Case %d:\n",ca++);
while(q--)
{
char s[];
scanf("%s",s);
if(s[]=='A')
{
scanf("%d%d",&u,&v);
update(u,v,,root);
node[tot++]=Node(u,v);
}
else
{
scanf("%d",&x);
if(t==){puts("");continue;}
for(i=last[x];i<tot;i++) //i是改点冷却好的时间点
{
if(x>=node[i].l&&x<=node[i].r) //防御成功
{
cnt[x]++;
last[x]=i+t;
i+=t-;
}
}
//printf("***%d %d***\n",query(x,root),cnt[x]);
printf("%d\n",query(x,root)-cnt[x]);
}
}
}
}