[NOIP2018模拟赛] 小P的太空旅行

65 阅读 0 评论 43 点赞

我是靠谱客的博主勤奋蜜粉，最近开发中收集的这篇文章主要介绍[NOIP2018模拟赛] 小P的太空旅行，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述:

今年是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
10 5 5 1
1 5 3 4 2 4 1 2 3 5 
1 10
3 6 
2 8
5 7
6 10
output
0
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

正解~~似乎是树状数组优化的莫队~~、但我只会裸的莫队，好在也没有卡

#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

然后输出答案就好了、

#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;
}