LightOJ 1118 树状数组+离线

83 阅读 0 评论 55 点赞

我是靠谱客的博主单薄鸵鸟，这篇文章主要介绍LightOJ 1118 树状数组+离线，现在分享给大家，希望可以做个参考。

题目大意:给出一个序列,每次询问(l,r)区间的不同的数的个数
思路:将每个询问按照r升序排序,若当前到达i,a[i]出现过,则之前位置-1,当前位置+1,若没有出现过则当前位置+1
为什么要sum[r]-sum[l-1]是对的:因为当前计算贡献的对应的有且只有一个,并且其值对应的位置是最新的位置
为什么按照升序排列:因为按照升序排列保证我们当前出现的值都在所要询问的区间之内.否则会出现它的值确实出现过在后面但不在当前区间内,而多算的情况

复制代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=1e5+10;
int n,q,a[N],pos[N],tr[N],ans[N];
struct ask{
    int l,r,id;
    bool operator < (const ask& rhs) const{
        return rhs.r==r?rhs.l<l:rhs.r>r;
    }
    ask(int l=0,int r=0,int id=0):l(l),r(r),id(id){}
}que[N];
#define lowbit(x) ((x)&(-x))
void update(int pos,int val)
{
    for(int i=pos;i<=n;i+=lowbit(i)) {
        tr[i]+=val;
    }
}
int query(int pos) {
    int ret=0;
    for(int i=pos;i;i-=lowbit(i)) {
        ret+=tr[i];
    }
    return ret;
}
void solve()
{
    int cur=1;
    for(int i=1;i<=q;i++) {
        while(cur<=que[i].r) {
            if(!pos[a[cur]]) pos[a[cur]]=cur,update(cur,1);
            else {update(cur,1);update(pos[a[cur]],-1);pos[a[cur]]=cur;}
            cur++;
        }cur--;
        if(cur==que[i].r) {
            int suml=query(que[i].l-1);
            int sumr=query(que[i].r);
            ans[que[i].id]=sumr-suml;
        }
    }  
}
int main()
{
    int T,kase=0;scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&q);
        fo(i,1,n) scanf("%d",&a[i]);
        for(int l,r,i=1;i<=q;i++) {
            scanf("%d%d",&l,&r);
            que[i]=ask(l,r,i);
        }
        memset(tr,0,sizeof(tr));
        memset(pos,0,sizeof(pos));
        sort(que+1,que+1+q);
        solve();
        printf("Case %d:n",++kase);
        for(int i=1;i<=q;i++) printf("%dn",ans[i]);    
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=1e5+10;
int n,q,a[N],pos[N],tr[N],ans[N];
struct ask{
    int l,r,id;
    bool operator < (const ask& rhs) const{
        return rhs.r==r?rhs.l<l:rhs.r>r;
    }
    ask(int l=0,int r=0,int id=0):l(l),r(r),id(id){}
}que[N];
#define lowbit(x) ((x)&(-x))
void update(int pos,int val)
{
    for(int i=pos;i<=n;i+=lowbit(i)) {
        tr[i]+=val;
    }
}
int query(int pos) {
    int ret=0;
    for(int i=pos;i;i-=lowbit(i)) {
        ret+=tr[i];
    }
    return ret;
}
void solve()
{
    int cur=1;
    for(int i=1;i<=q;i++) {
        while(cur<=que[i].r) {
            if(!pos[a[cur]]) pos[a[cur]]=cur,update(cur,1);
            else {update(cur,1);update(pos[a[cur]],-1);pos[a[cur]]=cur;}
            cur++;
        }cur--;
        if(cur==que[i].r) {
            int suml=query(que[i].l-1);
            int sumr=query(que[i].r);
            ans[que[i].id]=sumr-suml;
        }
    }  
}
int main()
{
    int T,kase=0;scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&q);
        fo(i,1,n) scanf("%d",&a[i]);
        for(int l,r,i=1;i<=q;i++) {
            scanf("%d%d",&l,&r);
            que[i]=ask(l,r,i);
        }
        memset(tr,0,sizeof(tr));
        memset(pos,0,sizeof(pos));
        sort(que+1,que+1+q);
        solve();
        printf("Case %d:n",++kase);
        for(int i=1;i<=q;i++) printf("%dn",ans[i]);    
    }
    return 0;
}