题解 P4113 【[HEOI2012]采花】
隔壁有道和这题题意和样例一毛一样的题。。。就是数据范围小了点。。。
题意大概：给出n个数，求区间出现次数>=2的数的个数。
建议做这题之前可以先去做hh的项链。
此题和那题做法类似。
我们只关心的是每个区间出现两次及以上的数的最后那个。
比如(1,2,3,2,3,1,1)，我们如果查询[1,7]，那么我们就可以把这个数列看成是(0,0,0,1,1,0,1)，然后用前缀和(用BIT维护)求出这个区间的答案。
具体怎么实现？
我用了一种离线的办法。
先把所有询问的区间都读进来，然后按l排序。
我们先对每个数第二次出现的位置标记为1。
因为现在l是有序的，我们可以从1开始往后搞，每次搞当前询问的l-1为止。如果与当前位置的数相同的下一个数的下一个数存在，我们就把那个数的位置标记为1，如果与当前位置的数相同的下一个数存在，说明我们之前把它标记过了，并且现在它不算了，因为要出现次数为>=2，而我们当前这个数已经不在是包含在询问的区间里的数了，所以它的下一个数肯定不是我们要标记的出现两次及以上的数的最后那个，所以我们要把它标记为0。
代码：
#include<cstdio>
#include<algorithm>
#include<string>
#include<set>
#include<vector>
#include<map>
#define For(i,x,y) for (int i=(x);i<=(y);i++)
#define Dow(i,x,y) for (int i=(x);i>=(y);i--)
#define cross(i,k) for (int i=first[k];i;i=last[i])
#define il inline
#define vd void
#define ll long long
#define N 2000010
using namespace std;
namespace fast_IO {
inline char read() {
return getchar();
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
if (s == t) {
t = (s = buf) + fread(buf, 1, IN_LEN, stdin);
if (s == t) return -1;
}
return *s++;
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig = false, c = read(); !isdigit(c); c = read()) {
if (c == '-') iosig = true;
if (c == -1) return;
}
for (x = 0; isdigit(c); c = read())
x = ((x + (x << 2)) << 1) + (c ^ '0');
if (iosig) x = -x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh = obuf;
inline void print(char c) {
if (ooh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh = obuf;
*ooh++ = c;
}
template<class T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) {
print('0');
}
else {
if (x < 0) print('-'), x = -x;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) print((char)buf[cnt--]);
}
}
inline void flush() {
fwrite(obuf, 1, ooh - obuf, stdout);
}
}
using namespace fast_IO;
struct node{
int l,r,id;
}q[N];
int c[N],ans[N],n,m,k,color[N],first[N],next[N],nnext[N],b[N];
il bool cmp(node x,node y){return x.l<y.l;}
il int lowbit(int x){return x&(-x);}
il vd add(int x,int y){
for(int i=x;i<=n;i+=lowbit(i)) c[i]+=y;
}
il int query(int x){
int sum=0;
for (int i=x;i>0;i-=lowbit(i)) sum+=c[i];
return sum;
}
int main(){
read(n),read(k),read(m);
For(i,1,n) read(color[i]);
Dow(i,n,1){
next[i]=first[color[i]];
first[color[i]]=i;
}
For(i,1,n)
nnext[i]=next[next[i]];
For(i,1,n)
if (++b[color[i]]==2) add(i,1);
For(i,1,m){
read(q[i].l),read(q[i].r);
q[i].id=i;
}
sort(q+1,q+1+m,cmp);
int now=1;
For(i,1,m){
for (;now<q[i].l;now++){
if (next[now]) add(next[now],-1);
if (nnext[now]) add(nnext[now],1);
}
ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
}
For(i,1,m) print(ans[i]),print('\n');
flush();
}
~~最后说一句：看到题目里的"萧薰儿"一下子就想到了斗破的动漫化，童年毁了啊~~