题目描述:
今年是8102年，小P去M870星球旅行了。M870星球景色优美，食物非常美味，所以全宇宙的人都爱去M870星球旅行。
这些来旅行的游客可以看作一排，来自不同星球的旅客的识别码是不同的，识别码是由1到k的，不同识别码表示不同星球的旅客。
小P想要知道，在一个区间里有多少种出现次数恰好为T次的旅客。
输入格式:
第一行四个整数n，m，k，T（1<=n,m,k,T<=5*10^5）。
第二行n个整数，第i个整数为a[i]，表示对应旅客的种族(1<=a[i]<=k)。
接下来m行，每行两个整数l[i]和r[i],表示询问的区间(1<=l[i]<=r[i]<=n)。
输出格式:
输出m行，每行一个整数，第i行表示第i次询问的答案。
样例:
input
复制代码1
2
3
4
5
6
7
810 5 5 1 1 5 3 4 2 4 1 2 3 5 1 10 3 6 2 8 5 7 6 10output
复制代码1
2
3
4
5
60 2 3 3 5数据范围与提示
对于30%的数据 n,m,k<=2000,T<=n.
对于另外40%的数据 T=1，1<=n,m,k<=5*10^5.
对于所有数据，1<=n,m,k,T<=5*10^5，1<=a[i]<=k,1<=l[i]<=r[i]<=n.
注意：本题输入量较大，请使用较为快速的读入方式。
题目链接、syzoj
正解似乎是树状数组优化的莫队、但我只会裸的莫队，好在也没有卡
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#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 5e5+7,mod = 1e9+7; int n,m,k,T,block; int a[maxn],ans[maxn],t[maxn]; struct node{int l,r,id;}p[maxn]; bool cmp(node a,node b){ if(a.l/block == b.l/block) return a.r<b.r; return a.l/block < b.l/block; } signed main(){ freopen("trip.in","r",stdin); freopen("trip.out","w",stdout); scanf("%d%d%d%d",&n,&m,&k,&T); block = sqrt(n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=m;i++)scanf("%d%d",&p[i].l,&p[i].r),p[i].id = i; sort(p+1,p+1+m,cmp); int l = 1,r = 0,tans = 0; for(int i=1;i<=m;i++){ while(l<p[i].l){ if(t[a[l]] == T)tans--; t[a[l]]--; if(t[a[l]] == T)tans++; l++; } while(l>p[i].l){ --l; if(t[a[l]] == T)tans--; t[a[l]]++; if(t[a[l]] == T)tans++; } while(r<p[i].r){ ++r; if(t[a[r]] == T)tans--; t[a[r]]++; if(t[a[r]] == T)tans++; } while(r>p[i].r){ if(t[a[r]] == T)tans--; t[a[r]]--; if(t[a[r]] == T)tans++; r--; } ans[p[i].id] = tans; } for(int i=1;i<=m;i++)printf("%dn",ans[i]); fclose(stdin); fclose(stdout); return 0; }
正解是一个考虑区间影响的思路、
预处理一下pre[a[i]]，即a[i]出现上一次的位置
询问是l到r，那么把询问按r从大到小排序，先考虑
r == n，那么枚举1到k，每一种向前找t个，如果没有t个就无所谓了
把now[i]定位到倒数第t个的位置，在这个位置上来说，若r位于pre[i]到now[i]的之间
那么i便是答案的一个(出现t次)，即ans++，怎么表现这个呢、
把tree[pre[i]]+=-1,tree[now[i]]+=1（此位置+1，前位置-1），这样query(r)-query(l-1)，就是答案了
那么枚举询问，因为r从大到小，所以设一个pos = n
每次讲pos移动到p[i].r的位置，然后ans[p[i].id]就等于query(p[i].r)-query(p[i].l-1)了
看下移动的时候的影响，相当于是将now[a[i]]的位置向前挪一下、
那么先将原来的影响取消，即
此位置，前位置，前前位置
-1 ，1 ，0
然后向前移动即
此位置，前位置，前前位置
0 ，1 ，-1
那么两者叠加就是
此位置，前位置，前前位置
-1 ，2 ，-1
然后输出答案就好了、
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#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 5e5+7,mod = 1e9+7; int n,m,k,t; int a[maxn],ans[maxn],tree[maxn],pre[maxn],now[maxn]; struct node{int l,r,id; }p[maxn]; bool cmp(node a,node b){return a.r>b.r;} void add(int pos,int val){ if(pos)while(pos<=n) tree[pos]+=val,pos+=pos&-pos; } int query(int pos,int ans = 0){ while(pos) ans+=tree[pos],pos-=pos&-pos; return ans; } signed main(){ //freopen("trip.in","r",stdin); //freopen("trip.out","w",stdout); scanf("%d%d%d%d",&n,&m,&k,&t); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); pre[i] = now[a[i]],now[a[i]] = i; } for(int i=1;i<=m;i++) scanf("%d%d",&p[i].l,&p[i].r),p[i].id = i; sort(p+1,p+1+m,cmp); for(int i=1;i<=k;i++){ int x = t-1; while(now[i] && x)x--,now[i] = pre[now[i]]; if(now[i])add(now[i],1),add(pre[now[i]],-1); } int pos = n; for(int i=1;i<=m;i++){ while(pos>p[i].r){ add(now[a[pos]],-1),add(pre[now[a[pos]]],2),add(pre[pre[now[a[pos]]]],-1); now[a[pos]] = pre[now[a[pos]]],pos--; } ans[p[i].id] = query(p[i].r) - query(p[i].l-1); } for(int i=1;i<=m;i++)printf("%dn",ans[i]); return 0; }
最后
以上就是勤奋蜜粉最近收集整理的关于[NOIP2018模拟赛] 小P的太空旅行的全部内容，更多相关[NOIP2018模拟赛]内容请搜索靠谱客的其他文章。
![【bzoj1917】[Ctsc2010]星际旅行](/uploads/reation/bcimg13.png)
![[NOIP2018模拟赛] 小P的太空旅行](/uploads/reation/bcimg14.png)
发表评论 取消回复