最近在做AC自动机的某些题目。。。结果发现很多题目要用到Fail树、DFS序以及区间维护查询。
于是树状数组经常被用到，而且常常是离线处理。
下面整理几道树状数组离线处理的题目。
BZOJ2743
【题意】
询问区间内出现超过一次的数的个数。
【思路】
离线处理。把询问区间按右端点从小到大排序。
对于某个位置，设标号比小且颜色与相同且标号最大的标号为.
若是第一次出现则.
从左到右扫描，扫到位置时,就把区间 的值都加1，同时对于所有右端点为的询问记录答案为左端点位置上的值。
显然可以用树状数组差分维护。
【代码】
/**************************************************************
Problem: 2743
User: wyfcyx
Language: C++
Result: Accepted
Time:4040 ms
Memory:32064 kb
****************************************************************/
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define lowbit(x) (x & -x)
inline char getc()
{
static int L = 4096;
static char buf[4096] , *S = buf , *T = buf;
if (S == T)
{
T = (S = buf) + fread(buf , 1 , L , stdin);
if (S == T)
return EOF;
}
return *S++;
}
inline int getint()
{
static char c;
while(!isdigit(c = getc()));
int tmp = c - '0';
while(isdigit(c = getc()))
tmp = (tmp << 1) + (tmp << 3) + c - '0';
return tmp;
}
int A[1000001] , n;
int Getsum(int x)
{
int ans = 0;
for(register int i = x ; i >= 1 ; i -= lowbit(i))
ans += A[i];
return ans;
}
void Modify(int x , int add)
{
for(register int i = x ; i <= n ; i += lowbit(i))
A[i] += add;
}
int prev[1000001] , ext[1000001] , col[1000001];
struct ask
{
int l , r , num;
bool operator < (const ask &b) const
{
return r < b.r;
}
}S[1000001];
int ans[1000001];
int main()
{
int c , m;
n = getint();
c = getint();
m = getint();
register int i;
for(i = 1 ; i <= n ; ++i)
{
col[i] = getint();
prev[i] = ext[col[i]];
ext[col[i]] = i;
}
for(i = 1 ; i <= m ; ++i)
{
S[i].l = getint();
S[i].r = getint();
S[i].num = i;
}
sort(S + 1 , S + m + 1);
int ins = 1;
for(i = 1 ; i <= n ; ++i)
{
if (prev[i] != 0)
{
Modify(prev[prev[i]] + 1, 1);
Modify(prev[i] + 1 , -1);
}
while(S[ins].r == i && ins <= m)
{
ans[S[ins].num] = Getsum(S[ins].l);
ins++;
}
}
for(i = 1 ; i <= m ; ++i)
printf("%d\n" , ans[i]);
return 0;
}
BZOJ1878
【题意】
询问区间内有多少种不同的数。
【做法】
把区间按照左端点从小到大排序。
枚举区间，并更新扫描线到区间左端点之前的后继，记录询问答案为区间和。
【代码】
/**************************************************************
Problem: 1878
User: wyfcyx
Language: C++
Result: Accepted
Time:920 ms
Memory:8428 kb
****************************************************************/
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define lowbit(x) (x & -x)
using namespace std;
inline int getint()
{
static char c;
while(!isdigit(c = getchar()));
int tmp = c - '0';
while(isdigit(c = getchar()))
tmp = (tmp << 1) + (tmp << 3) + c - '0';
return tmp;
}
const int N = 50001;
const int M = 1000001;
int next[N] , col[N] , last[M];
int A[N] , n;
int Getsum(int x)
{
int ans = 0;
for(register int i = x ; i >= 1 ; i -=lowbit(i))
ans += A[i];
return ans;
}
void Update(int x)
{
for(register int i = x ; i <= n ; i += lowbit(i))
A[i]++;
}
struct ask
{
int num , l , r;
bool operator < (const ask &b) const
{
return l < b.l;
}
}S[200001];
int ans[200001];
int main()
{
n = getint();
register int i , j , k;
for(i = 1 ; i <= n ; ++i)
col[i] = getint();
for(i = 1 ; i <= n ; ++i)
{
if (!last[col[i]])
{
last[col[i]] = 1;
Update(i);
}
}
memset(last , 0 , sizeof(last));
for(i = n ; i >= 1 ; --i)
{
if (!last[col[i]])
last[col[i]] = i;
next[i] = last[col[i]];
last[col[i]] = i;
}
int m;
scanf("%d" , &m);
for(i = 1 ; i <= m; ++i)
{
S[i].l = getint() , S[i].r = getint();
S[i].num = i;
}
sort(S + 1 , S + m + 1);
for(i = 1 , j = 0; i <= m ; ++i)
{
for(k = j + 1; k < S[i].l ; ++k)
if (next[k])
Update(next[k]);
j = S[i].l - 1;
ans[S[i].num] = Getsum(S[i].r) - Getsum(j);
}
for(i = 1 ; i <= m ; ++i)
printf("%d\n" , ans[i]);
return 0;
}
