题目描述
题解：
个人感觉这个题真不错。。。emmm。。
为什么这么说，这个题有多种做法：
1.树状数组
2.莫队算法
3.主席树
4.线段树
想讲讲我的做题过程，再讲正解
做题过程
第一反应就是树状数组
我想的很简单，只将第一次出现的数字插入到树状数组中，最后
记录[r,n]和[1,l]的答案
ll w=getsum(n)-getsum(r-1)+getsum(l);
结果只能过一半的数据，我想了一阵子也没想明白哪错了
对拍后发现自己想的太简单了
首先l有可能大于等于r
其次我只记录了每个数第一次出现的情况
但是这样不可，因为我们选取的区间很有可能根本没有选到某个数第一次出现的位置，但是有可能选到这个数第2次出现的情况
样例：
6 1
3 2 2 2 2 3
1 3
（详细见代码）
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+9;
typedef long long ll;
int a[maxn];
ll tree[maxn];
bool iff[maxn];
int n,q;
int lowbit(int x)
{
return x&(-x);
}
int getsum(int pos)
{
int sum=0;
while(pos)
{
sum+=tree[pos];
pos-=lowbit(pos);
}
return sum;
}
void add(int pos,int c)
{
while(pos<=n)
{
tree[pos]+=c;
pos+=lowbit(pos);
}
}
int main()
{
ios::sync_with_stdio(false);
while(cin>>n>>q)
{
int tot=0;
memset(tree,0,sizeof(tree));
memset(a,0,sizeof(a));
memset(iff,0,sizeof(iff));
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(iff[a[i]]==0)
{
iff[a[i]]=1;
add(i,1);
tot++;
}
}
while(q--)
{
int l,r;
cin>>l>>r;
if(l>=r)cout<<tot<<endl;
else
{
ll w=getsum(n)-getsum(r-1);
w+=getsum(l);
cout<<w<<endl;
}
}
}
return 0;
}后来我想既然这样，我们可以将数组延长
读入时进行操作a[i+n]=a[i]
这样区间[1,l]和[r,n]就可以合并为[r,1+n]
这样就可以直接一个for循环对树状数组操作，
但万万没注意数据范围是1e5，超时了。。。
又是过了百分之五十的数据
对拍时也能感受到明显的慢
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define random(a,b) ((a)+rand()%((b)-(a)+1))
stringstream ss;
int main( int argc, char *argv[] )
{
int seed=time(NULL);
if(argc)
{
ss.clear();
ss<<argv[1];
ss>>seed;
}
srand(seed);
//以上为随机数初始化，请勿修改
//random(a,b)生成[a,b]的随机整数
//以下写你自己的数据生成代码
//printf("1\n");
int i=1;
int n;
int m;
n=random(1,100000);
m=random(1,100000);
//freopen("data1.in","w",stdout);
printf("%d %d\n",n,m);
for(int i=1;i<=n;i++)
{
int x;
x=random(1,n);
printf("%d ",x);
}
cout<<endl;
for(int i=1;i<=m;i++)
{
int l,r;
l=random(1,n);
r=random(1,n);
cout<<l<<" "<<r<<endl;
}
//n=100000;
//m=100000;
// for(int i=1;i<=n;i++)
// {
// w=random(1,100);
// v=random(1,1000000000);
// printf("%d %lld\n",w,v);
// }
// for(int i=1 ; i<=n ; ++i)
// {
// for(int i=1;i<=m;i++)
// {
// if(random(0,1)==0)cout<<".";
// else cout<<"X";
// }
// cout<<endl;
// }
// printf("\n");
return 0;
}正解：
1.线段树
首先，我们可以用first来记录每个值第一次出现的位置
last来记录最后出现的位置
然后按照r由小到大排序
用了点莫队思想，r从1开始依次逼近，因为我们的查询是按照r从小到大排，所以每次查询完，r不用从头重新开始，这是一个优化的地方
剩下的就是常规操作
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn =2e5+100;
int a[maxn],ans[maxn],n;
int last[maxn],cnt[maxn];
int m,tot,first[maxn],r;
struct node
{
int l,r,id;
bool operator<(const node&b)const
{
return r<b.r;
}
} q[maxn];
void add(int x)
{
while(x<=n)
{
cnt[x]++;
x+=x&(-x);
}
}
int query(int x)
{
int ret=0;
while(x)
{
ret+=cnt[x];
x-=x&(-x);
}
return ret;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
memset(cnt,0,sizeof(cnt));
memset(last,0,sizeof(last));
memset(first,0,sizeof(first));
tot=0;
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
if(first[a[i]]==0)
{
first[a[i]]=i;
tot++;
}
last[a[i]]=i;
}
for(int i=1; i<=m; i++)
{
scanf("%d%d",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q+1,q+1+m);
r=1;
for(int i=1; i<=m; i++)
{
while(r<q[i].r)
{
if(last[a[r]]==r)
{
add(first[a[r]]);
tot--;
}
r++;
}
ans[q[i].id]=tot+query(q[i].l);
}
for(int i=1; i<=m; i++)
printf("%d\n",ans[i]);
}
return 0;
}莫队做法
我们完全可以用莫队实现离线查询（快算莫队裸题了）
这里莫队就不展开说了。。
分块时要将分块大小block_size由sqrt(n)改成固定的sqrt(maxn)，否则会t
我们还可以对查询也进行分块，这样更快
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 1e5 + 100;
typedef long long ll;
int n, a[maxn];
int q;
int block[maxn];
int cnt[maxn];
int cnt_dif;
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*10+ch-'0';ch=getchar();}
return x*f;
}
struct Query
{
int l, r, id;
int ans;
} querys[maxn];
bool cmp(const Query & x, const Query & y)
{
if (block[x.l] == block[y.l]) return x.r < y.r;
return x.l < y.l;
}
bool cmp_id(const Query & x, const Query & y)
{
return x.id < y.id;
}
void update(int p, int add)
{
if (add == -1)
{
if (cnt[a[p]] == 1) --cnt_dif;
cnt[a[p]]--;
}
else
{
if (cnt[a[p]] == 0) ++cnt_dif;
cnt[a[p]]++;
}
}
int main()
{
while (scanf("%d%d", &n, &q) == 2)
{
memset(cnt, 0, sizeof(int) * (1 + n));
cnt_dif = 0;
for (int i = 1; i <= n; ++i)
{
a[i] = read();
if (cnt[a[i]] == 0) ++cnt_dif;
cnt[a[i]]++;
}
int block_size = (int)sqrt(maxn);
for (int i = 1; i <= n; ++i)
block[i] = (i - 1) / block_size + 1;
for (int i = 1; i <= q; ++i)
{
querys[i].l = read();
querys[i].r = read();
if (querys[i].l >= querys[i].r) querys[i].r = querys[i].l + 1;
querys[i].id = i;
}
sort(querys + 1, querys + 1 + q, cmp);
int l = 1, r = 2;
for (int i = 1; i <= q; ++i)
{
for (; r < querys[i].r; ++r) update(r, -1);
for (; r > querys[i].r; --r) update(r - 1, 1);
for (; l < querys[i].l; ++l) update(l + 1, 1);
for (; l > querys[i].l; --l) update(l, -1);
querys[i].ans = cnt_dif;
}
sort(querys + 1, querys + 1 + q, cmp_id);
for (int i = 1; i <= q; ++i) printf("%d\n", querys[i].ans);
}
return 0;
}主席树
把n个数倍增，即a[i+n]=a[i]。这样的话求[1,L]和[R,n]两个区间合并后的数字种类数变成求[R,L+n]中的数字的种类数
变成了经典的主席树入门题
关于修改
序列扫一遍，如果这个数字没有出现过，那么就直接以这个点作划分，其新的链+1表示区间上都了一种数
如果没有出现，那么找出同一个数上一次出现的位置（可以用数组标记实现）j，这样把第j个链的划分-1，并在当前链的划分+1使得区间中数字不重复，而只保留最后一个。
关于查询
如果我们要查询的区间为[L,R]，那么我们就以L为划分依据，在第R个链上查询，当发现可以向左走的时候，我们直接+右儿子的sum并递归到左儿子；反之时不用加，因为会加多（因为我们都是以最后的出现的地方为划分依据的）。
代码：
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#include<cstdio>
#include<functional>
#include<iomanip>
#include<cmath>
#include<stack>
#include<iomanip>
#include<functional>
#include <iomanip>
#include<bitset>
#define lson l,m
#define rson m+1,r
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
const int maxn = 2 * int(1e5) + 100;
const int BN = 30;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = (int)1e9 + 7;
const double eps = 1e-6;
int read() { //输入挂
int x = 0, f = 1; register char ch = getchar();
while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
return x*f;
}
struct nodes {
int l, r, sum;
}tr[maxn*40];
int root[maxn], tot;
int build(int l, int r) {
int rt = ++tot;
tr[rt].sum = 0;
tr[rt].l = tr[rt].r = 0;
if (l == r) return rt;
int m = (l + r) >> 1;
tr[rt].l = build(lson);
tr[rt].r = build(rson);
return rt;
}
int update(int pos, int c, int v, int l, int r) {
int rt = ++tot;
tr[rt] = tr[c];
tr[rt].sum += v;
if (l == r) return rt;
int m = (l + r) >> 1;
if (m >= pos) tr[rt].l = update(pos, tr[c].l, v, lson);
else tr[rt].r = update(pos, tr[c].r, v, rson);
return rt;
}
int query(int pos, int c, int l, int r) {
if (l == r) return tr[c].sum;
int m = (l + r) >> 1;
if (m >= pos)return tr[tr[c].r].sum + query(pos, tr[c].l, lson);
else return query(pos, tr[c].r, rson);
}
int vis[maxn], num[maxn];
int main() {
//freopen("D:\\cpp\\dates\\test.txt", "r", stdin);
int n, q;
while (~scanf("%d%d", &n, &q)) {
memset(vis, -1, sizeof(vis));
tot = 0;
for (int i = 1; i <= n; i++) {
num[i] = read();
num[i + n] = num[i];
}
root[0] = build(1, 2 * n);
for (int i = 1; i <= 2 * n; i++) {
int v = num[i];
if (vis[v] == -1)
root[i] = update(i, root[i - 1], 1, 1, 2 * n);
else {
int t = update(vis[v], root[i - 1], -1, 1, 2 * n);
root[i] = update(i, t, 1, 1, 2 * n);
}
vis[v] = i;
}
while (q--) {
int x = read(), y = read();
printf("%d\n", query(y, root[x + n], 1, 2 * n));
}
}
return 0;
}线段树
线段树和树状数组差不多，这就不细讲了
京公网安备 11010502036488号