首页 > 分享 > [HEOI2012] 树状数组 + 离线预处理超详解【校队排位赛#12 J】

[HEOI2012] 树状数组 + 离线预处理超详解【校队排位赛#12 J】

花匠小妙招
2024-09-10 13:42

Description
萧芸斓是Z国的公主，平时的一大爱好是采花。今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花
。花园足够大，容纳了n朵花，花有c种颜色（用整数1-c表示），且花是排成一排的，以便于公主采花。公主每次
采花后会统计采到的花的颜色数，颜色数越多她会越高兴！同时，她有一癖好，她不允许最后自己采到的花中，某
一颜色的花只有一朵。为此，公主每采一朵花，要么此前已采到此颜色的花，要么有相当正确的直觉告诉她，她必
能再次采到此颜色的花。由于时间关系，公主只能走过花园连续的一段进行采花，便让女仆福涵洁安排行程。福涵
洁综合各种因素拟定了m个行程，然后一一向你询问公主能采到多少朵花（她知道你是编程高手，定能快速给出答
案！），最后会选择令公主最高兴的行程（为了拿到更多奖金！）。
Input
第一行四个空格隔开的整数n、c以及m。
接下来一行n个空格隔开的整数，每个数在[1, c]间，第i个数表示第i朵花的颜色。
接下来m行每行两个空格隔开的整数l和r（l ≤ r），表示女仆安排的行程为公主经过第l到第r朵花进行采花。
Output
共m行，每行一个整数，第i个数表示公主在女仆的第i个行程中能采到的花的颜色数。
Sample Input
5 3 5

1 2 2 3 1

1 5

1 2

2 2

2 3

3 5
Sample Output
2

【样例说明】

询问[1, 5]：公主采颜色为1和2的花，由于颜色3的花只有一朵，公主不采；询问[1, 2]：颜色1和颜色2的花均只有一朵，公主不采；

询问[2, 2]：颜色2的花只有一朵，公主不采；

询问[2, 3]：由于颜色2的花有两朵，公主采颜色2的花；

询问[3, 5]：颜色1、2、3的花各一朵，公主不采。

HINT
【数据范围】

对于100%的数据，1 ≤ n ≤ 10^6，c ≤ n，m ≤10^6。

题意：若干询问，找出以区间内出现次数超过1次的数的个数

思路：

一开始用莫队，把能优化的地方都优化了，还是无情TL。再回去看一眼数据范围——1e6，好吧果断放弃。

那么树状数组or线段树无疑要临危受命了。问题是怎么构建模型了。这和之前那道求区间内有多少不同的还不一样，这个要出现2次及以上的才算一种。

但是用树状数组时，会遇到一个问题就是，怎么消去区间【L,R】之前的影响。
比如我要求 1 1 1 1 2 3 4 在【3,5】上的种类，我得消除【1,2】上的影响，因为我们想通过sum[5] - sum[2]来求的【3,5】上的值，sum[i]表示到 i 位置一共有多少种花。

我们希望有一个效果，在出现两个相同的时候有+1的效果，再多了就没有了，而且这两步最好能用一个方式实现。那么，就有了前缀数组。我可以用一个pre数组来表示这个位置前面一个相同元素的位置。我们的预处理就是记录每个元素的pre[i]和pre[ pre[i] ] ，因为我们是两个相同才开始计数，所以要记录前两个相同元素的位置。然后每次遍历到 i ，我们就将【pre[i], i】区间 + 1（也就是对pre[i]单点修改+1）,对于pre[pre[i]]点-1，然后这些有相同指向的点，就由这些1和-1组成。这有什么作用呢？

比如上面这个数据1 1 1 1 2 3 4

i = 1：没有前置，不管
i = 2：pre[1]=1, 该位置+1，那么【1,2】区间就是1，有一朵花可以采了哈。（没有pre[pre[i]]不管）
i = 3：pre[2] = 2，该位置+1，pre[pre[2]] = 1，该位置-1，诶？有什么效果呢？发现i=1位置的1被减掉了，而取而代之的是i=2的点变成1，这样我们发现前三个1总共的种类和还是0+1=1 。神奇吧？
i =4：pre[4] = 3 , 3位置+1， 2位置-1 。前四个种类和依旧是1。
后面也是类似情况。这样就完美解决了。

注意这样操作的时候，要把询问离线后按照右端点升序排列，逐个和 i 比较。因为我们线性这样处理过来，不断更新右端点，前面的区间是用来维护右端点的，你不能再倒回去找子区间，不然会出大问题。比如上面那个例子，你遍历到 i = 4时，你再回去询问【1,2】，这时候1 , 2这两个点为了和右端点匹配，已经变成0了，这时候询问结果也只是返回0+0=0 。这就是为什么要按照右端点排序且找和右端点匹配的点的原因了！

#include <iostream> #include <vector> #include <cstdio> #include <map> #include <climits> #include <string> #include <cmath> #include <cstring> #include <stack> #include <queue> #include <algorithm> #define maxn 1110000+500 using namespace std; typedef long long ll; typedef struct Query{ int l; int r; int k; }Q; Q q[maxn]; ll a[maxn]; ll c[maxn]; ll nxt[maxn]; //这里用nxt表示前一个位置（题解里面的pre） ll pre[maxn]; //这里的pre用来存a[i]这个元素的当前位置，用于下一次赋给nxt。 ll Ans[maxn]; //离线后用来存第几个询问结果的Ans ll n; bool cmp(Q a, Q b) //按照右端点排序 { return a.r<b.r; } inline int read(){ //快读 int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } void printi(int x) { //快写 if(x / 10) printi(x / 10); putchar(x % 10 + '0'); } int lowbit(int x) //树状数组模板，不多说 { return x&(-x); } void update(int x,int y){ for(int i=x;i<=n;i+=lowbit(i))c[i]+=y; } int getsum(int x){ int ans = 0; for(int i=x;i>=1;i-=lowbit(i)) ans += c[i]; return ans; } int main() { //cin>>n>>c>>m ios::sync_with_stdio(false); int c,m; scanf("%d%d%d",&n,&c,&m); for(int i=1;i<=n;i++) //预处理 { nxt[i] = 0; pre[i] =0; } for(int i=1;i<=n;i++) //读入 { a[i]= read(); } for(int i=1;i<=m;i++) { q[i]. l = read(); q[i].r = read(); q[i].k = i; } for(int i=1;i<=n;i++) //生产nxt数组 { nxt[i] = pre[a[i]]; pre[a[i]] = i; } sort(q+1,q+1+m,cmp); //按照右端点排序 int pos = 1; for( int i=1; i<=n; i++) //核心代码 { if(nxt[nxt[i]]!=0) //将前两次出现的位置-1 update(nxt[nxt[i]],-1); if(nxt[i]!=0)update(nxt[i],1); //前一次出现的位置+1while(q[pos].r==i) //若该点是询问的右端点，那就直接有了这个询问的结果了{ Ans[q[pos].k]=getsum(q[pos].r)-getsum(q[pos].l-1); pos++;}if(pos==m+1) break; } for(int i=1;i<=m;i++) { printi(Ans[i]); putchar('n'); } return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118