當(dāng)前位置: 首頁(yè)IT技術(shù) → HDU 4031 樹(shù)狀數(shù)組 區(qū)間更新及點(diǎn)詢問(wèn)

HDU 4031 樹(shù)狀數(shù)組 區(qū)間更新及點(diǎn)詢問(wèn)

更多

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

去年成都賽區(qū)網(wǎng)絡(luò)賽一道題,樹(shù)狀數(shù)組在區(qū)間更新中的應(yīng)用。樹(shù)狀數(shù)組一般支持的是改點(diǎn),查區(qū)間,但

是這道題要求的是改區(qū)間,查點(diǎn),這就要變通一下,具體可以看代碼,另外要考慮的一個(gè)問(wèn)題是,如何統(tǒng)計(jì)?

這里的處理方法就是把總共的攻擊次數(shù)-防御的次數(shù),因?yàn)閷?duì)單個(gè)點(diǎn)的詢問(wèn)可能有多次,所以為每個(gè)點(diǎn)都設(shè)

定一個(gè)游標(biāo)來(lái)優(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

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

熱門評(píng)論
最新評(píng)論
發(fā)表評(píng)論 查看所有評(píng)論(0)
昵稱:
表情: 高興 可 汗 我不要 害羞 好 下下下 送花 屎 親親
字?jǐn)?shù): 0/500 (您的評(píng)論需要經(jīng)過(guò)審核才能顯示)