[Solution][Data Structure][Lowbit]BZOJ2743 & 1878

最近在做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;
}
comments powered by Disqus