HDU 4031 樹狀數(shù)組 區(qū)間更新及點(diǎn)詢問
/*******************************************************************************
去年成都賽區(qū)網(wǎng)絡(luò)賽一道題，樹狀數(shù)組在區(qū)間更新中的應(yīng)用。樹狀數(shù)組一般支持的是改點(diǎn)，查區(qū)間，但
是這道題要求的是改區(qū)間，查點(diǎn)，這就要變通一下，具體可以看代碼，另外要考慮的一個(gè)問題是，如何統(tǒng)計(jì)？
這里的處理方法就是把總共的攻擊次數(shù)-防御的次數(shù)，因?yàn)閷?duì)單個(gè)點(diǎn)的詢問可能有多次，所以為每個(gè)點(diǎn)都設(shè)
定一個(gè)游標(biāo)來優(yōu)化時(shí)間～
*******************************************************************************/
#include
#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
*******************************************************************************/
