题目大意
给定一个序列,求区间出现次数为2次的数字有多少?
\(n \leq 10^6\)
思路一
首先处理出第\(i\)个数上次出现的位置\(pre_0\),上上次出现的次数\(pre_1\),维护一个权值数组表示到第\(i\)个位置时的数字分布情况。
和HH的项链一样,离线查询维护即可。
由于答案具有前缀和性质,用树状数组维护即可。
代码一
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int pre[N][2];
int n;
int c[N];
int a[N];
int l,r;
int m;
int ans[N];
struct node {
int id;
int pos;
node (int _id,int _pos) {
id = _id;
pos = _pos;
}
};
vector <node> q[N];
int lowbit(int x) {
return x & -x;
}
void modify(int x,int v) {
while(x <= n) {
c[x] += v;
x += lowbit(x);
}
}
int query(int x) {
int ans = 0;
while(x) {
ans += c[x];
x -= lowbit(x);
}
return ans;
}
int t;
int main () {
cin >> n >> t >> m;
for(int i = 1;i <= n; i ++) scanf("%d",&a[i]);
for(int i = 1;i <= m; i ++) {
scanf("%d %d",&l,&r);
q[r].push_back(node(i,l));
}
for(int i = 1;i <= n; i ++) {
if(pre[a[i]][1]) {
modify(pre[a[i]][1],-1);
modify(pre[a[i]][0],1);
}
else if(pre[a[i]][0]) {
modify(pre[a[i]][0],1);
}
pre[a[i]][1] = pre[a[i]][0];
pre[a[i]][0] = i;
int len = q[i].size();
for(int j = 0;j < len; j ++) {
node y = q[i][j];
ans[y.id] = query(i) - query(y.pos - 1);
}
}
for(int i = 1;i <= m; i ++) {
printf("%d\n",ans[i]);
}
return 0;
}
思路二
同思路一情况,需维护数组pre,使用主席树在线维护即可。
代码二
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
const int M = (N << 2) + 50;
int last[N];
int pre[N];
struct seg_tree {
int sum[M];
int lch[M];
int rch[M];
int rt[N];
int tot = 0;
void insert(int l,int r,int &root,int old,int pos) {
root = ++tot;
sum[root] = sum[old];
lch[root] = lch[old];
rch[root] = rch[old];
if (l == r) {
sum[root] ++;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid) {
insert(l,mid,lch[root],lch[old],pos);
}else {
insert(mid + 1,r,rch[root],rch[old],pos);
}
sum[root] = sum[lch[root]] + sum[rch[root]];
}
int query (int l,int r,int s,int t,int ql,int qr) {
if(ql == l and r == qr) {
return sum[t] - sum[s];
}
int mid = (l + r) >> 1;
int _s = 0;
if(qr <= mid) {
_s += query(l,mid,lch[s],lch[t],ql,qr);
}
else if(ql > mid) {
_s += query(mid + 1,r,rch[s],rch[t],ql,qr);
}else {
_s += query(l,mid,lch[s],lch[t],ql,mid) + query(mid + 1,r,rch[s],rch[t],mid + 1,qr);
}
return _s;
}
} ST1,ST2;
int n,c,m;
int main () {
scanf("%d %d %d",&n,&c,&m);
for(int i = 1;i <= n; i ++) {
int x;
scanf("%d",&x);
pre[i] = last[x];
last[x] = i;
}
for(int i = 1;i <= n; i ++) {
ST1.insert(0,n,ST1.rt[i],ST1.rt[i - 1],pre[i]);
ST2.insert(0,n,ST2.rt[i],ST2.rt[i - 1],pre[pre[i]]);
}
while(m --) {
int l,r;
scanf("%d %d",&l,&r);
int ans = ST1.query(0,n,ST1.rt[l - 1],ST1.rt[r],l,r) - ST2.query(0,n,ST2.rt[l - 1],ST2.rt[r],l,r);
printf("%d\n",ans);
}
return 0;
}