【SWTR-02】Picking Gifts

直接离线即可.对于每一步都存值即可.(凡是难做的题,都可以考虑离线.)
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5,M=5e5+5;
int ans[M],p[N],v[N],l[M],sum[N],n;
vector<int>r[N];//这个点是第几次查询的时候.
vector<int>kind[N];//记录下种类有多少个了.
int lowbit(int x) { return x&(-x); }

void add(int pos,int val)
{
    while(pos<=n)
    {
        sum[pos]+=val;
        pos+=lowbit(pos);
    }
}

int query(int pos)
{
    int res=0;
    while(pos)
    {
        res+=sum[pos];
        pos-=lowbit(pos);
    }
    return res;
}
int main()
{
    int m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)   scanf("%d",&p[i]);
    for(int i=1;i<=n;i++)   {scanf("%d",&v[i]);add(i,v[i]);}
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&l[i]);
        int R;scanf("%d",&R);
        r[R].push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
        kind[p[i]].push_back(i);
        if(kind[p[i]].size()>=k)
        {
            int pos=kind[p[i]][kind[p[i]].size()-k];
            add(pos,-v[pos]);
        }
        for(int j=0;j<r[i].size();j++)
        {
            ans[r[i][j]]=query(i)-query(l[r[i][j]]-1);
        }
    }
    for(int i=1;i<=m;i++)   printf("%d\n",ans[i]);
    return 0;
}