Problem Description

Today is the 10th Annual of “September 11 attacks”, the Al Qaeda is about to attack American again. However, American is protected by a high wall this time, which can be treating as a segment with length N. Al Qaeda has a super weapon, every second it can attack a continuous range of the wall. American deployed N energy shield. Each one defends one unit length of the wall. However, after the shield defends one attack, it needs t seconds to cool down. If the shield defends an attack at kth second, it can’t defend any attack between (k+1)th second and (k+t-1)th second, inclusive. The shield will defend automatically when it is under attack if it is ready.

During the war, it is very important to understand the situation of both self and the enemy. So the commanders of American want to know how much time some part of the wall is successfully attacked. Successfully attacked means that the attack is not defended by the shield.

 

Input

The beginning of the data is an integer T (T ≤ 20), the number of test case.
The first line of each test case is three integers, N, Q, t, the length of the wall, the number of attacks and queries, and the time each shield needs to cool down.
The next Q lines each describe one attack or one query. It may be one of the following formats
1. Attack si ti
  Al Qaeda attack the wall from si to ti, inclusive. 1 ≤ si ≤ ti ≤ N
2. Query p
  How many times the pth unit have been successfully attacked. 1 ≤ p ≤ N
The kth attack happened at the kth second. Queries don’t take time.
1 ≤ N, Q ≤ 20000
1 ≤ t ≤ 50

 

Output

For the ith case, output one line “Case i: ” at first. Then for each query, output one line containing one integer, the number of time the pth unit was successfully attacked when asked.

 

Sample Input

 

Sample Output

 

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<sstream>

#include<cstring>

#include<bitset>

#include<cstdio>

#include<string>

#include<deque>

#include<stack>

#include<cmath>

#include<queue>

#include<set>

#include<map>

using namespace std;

#define INF 0x3f3f3f3f

#define CLR(x,y) memset(x,y,sizeof(x))

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

typedef pair<int,int> pii;

typedef long long LL;

const double PI=acos(-1.0);

const int N=20010;

struct seg

{

	int l,mid,r;

	int sum,add;

};

seg T[N<<2];

int n,q,t;

void pushup(int k)

{

	T[k].sum=T[LC(k)].sum+T[RC(k)].sum;

}

void pushdown(int k)

{

	if(T[k].add)

	{

		T[LC(k)].add+=T[k].add;

		T[LC(k)].sum+=T[k].add*(T[LC(k)].r-T[LC(k)].l+1);

		T[RC(k)].add+=T[k].add;

		T[RC(k)].sum+=T[k].add*(T[RC(k)].r-T[RC(k)].l+1);

		T[k].add=0;

	}

}

void build(int k,int l,int r)

{

	T[k].l=l;

	T[k].r=r;

	T[k].mid=MID(l,r);

	T[k].add=T[k].sum=0;

	if(l==r)

		return ;

	else

	{

		build(LC(k),l,T[k].mid);

		build(RC(k),T[k].mid+1,r);

		pushup(k);

	}

}

void update(int k,int l,int r,int val)

{

	if(r<T[k].l||l>T[k].r)

		return ;

	if(l<=T[k].l&&r>=T[k].r)

	{

		T[k].add+=val;

		T[k].sum+=val*(T[k].r-T[k].l+1);

	}

	else

	{

		pushdown(k);

		update(LC(k),l,r,val);

		update(RC(k),l,r,val);

		pushup(k);

	}

}

int query(int k,int x)

{

	if(T[k].l==T[k].r&&T[k].l==x)

		return T[k].sum;

	pushdown(k);

	if(x<=T[k].mid)

		return query(LC(k),x);

	else if(x>T[k].mid)

		return query(RC(k),x);

}

pii range[N];

int pre[N];

int d[N];

int main(void)

{

	int l,r,i,x,cur;

	int tcase;

	char ops[8];

	scanf("%d",&tcase);

	for (int c=1; c<=tcase; ++c)

	{

		int cnt=0;

		CLR(pre,0);

		CLR(d,0);

		scanf("%d%d%d",&n,&q,&t);

		build(1,1,n);

		printf("Case %d:\n",c);

		while (q--)

		{

			scanf("%s",ops);

			if(ops[0]=='A')

			{

				scanf("%d%d",&l,&r);

				update(1,l,r,1);

				range[cnt++]=pii(l,r);

			}

			else

			{

				scanf("%d",&x);

				int total=query(1,x);

				for (cur=pre[x]; cur<cnt; )//范围就是上一次询问时间pre[x]到此次询问时间cnt

				{

					if(range[cur].first<=x&&x<=range[cur].second)

					{

						++d[x];

						pre[x]=cur+t;//最近询问时间更新

						cur+=t;//在此之后的t-1个都会防御失败，跳到第cur+t个

					}

					else

						++cur;

				}

				printf("%d\n",total-d[x]);

			}

		}

	}

	return 0;

}

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<sstream>

#include<cstring>

#include<bitset>

#include<cstdio>

#include<string>

#include<deque>

#include<stack>

#include<cmath>

#include<queue>

#include<set>

#include<map>

using namespace std;

#define INF 0x3f3f3f3f

#define CLR(x,y) memset(x,y,sizeof(x))

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

typedef pair<int,int> pii;

typedef long long LL;

const double PI=acos(-1.0);

const int N=20010;

int T[N];

void add(int k,int val)

{

	while (k<N)

	{

		T[k]+=val;

		k+=(k&-k);

	}

}

int getsum(int k)

{

	int r=0;

	while (k)

	{

		r+=T[k];

		k-=(k&-k);

	}

	return r;

}

pii range[N];

int pre[N];

int d[N];

int n,q,t;

int main(void)

{

	int l,r,i,x,cur;

	int tcase;

	char ops[8];

	scanf("%d",&tcase);

	for (int c=1; c<=tcase; ++c)

	{

		int cnt=0;

		CLR(pre,0);

		CLR(d,0);

		CLR(T,0);

		scanf("%d%d%d",&n,&q,&t);

		printf("Case %d:\n",c);

		while (q--)

		{

			scanf("%s",ops);

			if(ops[0]=='A')

			{

				scanf("%d%d",&l,&r);

				add(l,1);

				add(r+1,-1);

				range[cnt++]=pii(l,r);

			}

			else

			{

				scanf("%d",&x);

				int total=getsum(x);

				for (cur=pre[x]; cur<cnt; )//范围就是上一次询问时间pre[x]到此次询问时间cnt

				{

					if(range[cur].first<=x&&x<=range[cur].second)

					{

						++d[x];

						pre[x]=cur+t;//询问时间更新

						cur+=t;//在此之后的t-1个都会防御失败，跳到第cur+t个

					}

					else

						++cur;

				}

				printf("%d\n",total-d[x]);

			}

		}

	}

	return 0;

}