题解：P11497 [ROIR 2019 Day 1] 自动仓库

· · 题解

退役选手消磨元旦。想出做法以后板子调了半个多小时，然后不会 T4DP。

首先发现题目要求输出所有操作，于是可以猜到总操作次数一定不会太大。尝试分析总操作次数的量级。发现可以采用贪心策略，每次取出一把钥匙，那么就要把它插入到在它下一次用到之前所有需要用到的钥匙里最靠后的钥匙之前。也就是说我们可以保证下一次用这个钥匙的时候一定可以立刻抽到它。

于是总操作次数一点小于等于 n+m。因为抽出来一次以后下次抽它就一定是用它。

然后顺着这个贪心策略考虑怎么计算答案。

由于钥匙不能存手里。所以我们发现拿出来一个钥匙到下一次用它之间的所有钥匙一定还在槽里，如果这里面有没被拿出来过的钥匙，就用没被拿出来的最靠后的位置来计算答案。如果它们全被拿过了，那么此时钥匙槽里最前面的一定就是这些钥匙，也就是说我们只需要数一下在询问序列里两次询问当前钥匙之间有多少个不同的钥匙即可。

而且我们发现实际上询问都不需要在线。于是变成了经典的离线区间数颜色问题。

不过为了方便我把这两种情况都统一成了数颜色，具体来说就是把抽出钥匙的序列处理出来弄成一个新序列，这样既包含了询问序列，也包含了不得不抽出来的钥匙，在这个新序列上整体数颜色即可。

我一开始写的莫队。然后卡了十多分钟块长卡不过去。

后来改成树状数组就过了。

赛时代码。

#include<bits/stdc++.h>
using namespace std;

inline int qr() {
    int k=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')f=-1; ch=getchar();}
    while(isdigit(ch)){k=(k<<1)+(k<<3)+(ch^48);ch=getchar();}
    return k*f;
}

typedef long long ll;
const int mod=1e9+7;
const int N=3e5+2;

struct node{
    int l,r,id;
}q[N*2];

int n,m,a[N],b[N],d[N*2];//d数列即为处理出来的抽出序列
ll ans[N*2],siz;
int id[N];

int t[N*2];
inline void add(int x,int p) {
    while(x<=siz) t[x]+=p,x+=x&-x;
}
inline int ask(int x) {
    int rt=0;
    while(x) rt+=t[x],x-=x&-x;
    return rt;
}
inline int Ask(int l,int r) {
    return ask(r)-ask(l-1);
}
int pl[N];

inline void solve() {
    cin>>n>>m;
    for(int i=1;i<=m;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1,p=1;i<=m;i++) {
        if(id[a[i]]) {
            q[id[a[i]]].r=siz++;
            d[siz]=a[i];
            q[siz].l=siz+1;
            q[siz].id=id[a[i]]=siz;
            continue;
        }
        while(p<=n) {
            id[b[p]]=++siz;
            d[siz]=b[p];
            q[siz].l=siz+1;
            q[siz].id=siz;
            if(b[p++]==a[i]) break;
        }
    }
    sort(q+1,q+siz+1,[](node x,node y){return x.l>y.l;});
    q[0].l=siz+1;
    for(int i=1;i<=siz;i++) {
        for(int j=q[i-1].l-1;j>=q[i].l;j--) {
            add(j,1);
            if(pl[d[j]]) add(pl[d[j]],-1);
            pl[d[j]]=j;
        }
        if(!q[i].r) {ans[q[i].id]=n;continue;}
        ans[q[i].id]=Ask(q[i].l,q[i].r)+1;
    }

    cout<<siz<<'\n';
    for(int i=1;i<=siz;i++) cout<<ans[i]<<' ';

}

int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    // freopen("test.in","r",stdin);
    // freopen("test.out","w",stdout);
    solve();

    return 0;
}