HDU 4031 树状数组 区间更新及点询问

/*******************************************************************************

去年成都赛区网络赛一道题，树状数组在区间更新中的应用。树状数组一般支持的是改点，查区间，但

是这道题要求的是改区间，查点，这就要变通一下，具体可以看代码，另外要考虑的一个问题是，如何统计？

这里的处理方法就是把总共的攻击次数-防御的次数，因为对单个点的询问可能有多次，所以为每个点都设

定一个游标来优化时间～

*******************************************************************************/

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

#define LOWBIT(x) ( (x) & ( (x) ^ ( (x) - 1 ) ) )

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

#define CPY(t, s) memcpy((t), (s), sizeof(s))

#define SC(t, s) static_cast(s)

#define LEN(s) static_cast( strlen((s)) )

#define SZ(s) static_cast( (s).size() )

typedef double LF;

typedef __int64 LL; //VC

typedef unsigned __int64 ULL;

typedef pair PII;

typedef pair PLL;

typedef pair PDD;

typedef vector VI;

typedef vector VC;

typedef vector VF;

typedef vector VS;

template

T sqa(const T & x) {return x * x;}

template

T ll(const T & x) {return x << 1;}

template

T rr(const T & x) {return x << 1 | 1;}

template

T gcd(T a, T b)

{

if (!a || !b)

{

return max(a, b);

}

T t;

while (t = a % b)

{

a = b;

b = t;

}

return b;

};

const int INF_INT = 0x3f3f3f3f;

const LL INF_LL = 0x7fffffffffffffffLL; //15f

const double oo = 10e9;

const double eps = 10e-7;

const double PI = acos(-1.0);

#define ONLINE_JUDGE

const int MAXN = 20004;

int test, n, q, t;

int tree[MAXN];

int crs[MAXN], def[MAXN];

vector vp;

void updateBIT(int x, int inc)

{

for (int i = x; i > 0; i -= LOWBIT(i))

{

tree[i] += inc;

}

return ;

}

void updateSeg(int l, int r, int inc)

{

updateBIT(l - 1, -inc);

updateBIT(r, inc);

return ;

}

int queryBIT(int x)

{

int sum = 0;

for (int i = x; i <= n; i += LOWBIT(i))

{

sum += tree[i];

}

return sum;

}

void ace()

{

int cas = 1;

char op[10];

int l, r, p;

for (scanf("%d", &test); test--; ++cas)

{

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

CLR(tree, 0);

CLR(crs, 0);

CLR(def, 0);

vp.clear();

int ind = 0;

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

while (q--)

{

scanf("%s", op);

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

{

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

if (l > r)

{

swap(l, r);

}

//l = max(l, 1);

//r = min(r, n);

updateSeg(l, r, 1);

vp.push_back(PII(l, r));

++ind;

}

else

{

scanf("%d", &p);

if (1 == t)

{

puts("0");

continue ;

}

int token = 0;

while (crs[p] < ind)

{

if (vp[ crs[p] ].first <= p && p <= vp[ crs[p] ].second)

{

if (0 == token % t)

{

crs[p] += t - 1;

++def[p];

token = t - 1;

}

++token;

}

++crs[p];

}

printf("%d\n", queryBIT(p) - def[p]);

}

}

}

return ;

}

int main()

{

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

freopen("out.txt", "w", stdout);

#endif

ace();

return 0;

}

/*******************************************************************************

Test Data...

2

3 7 2

Attack 1 2

Query 2

Attack 2 3

Query 2

Attack 1 3

Query 1

Query 3

9 7 3

Attack 5 5

Attack 4 6

Attack 3 7

Attack 2 8

Attack 1 9

Query 5

Query 3

*******************************************************************************/