题目概述

Jewel Grab

解题报告

因为 $k\le 10$ ，其实就是个暴力题。

记录 $pre_x$ 表示 $x$ 前面第一个颜色相同的位置（没有就记成 $0$ ），如果不能跳过，那么一定是在 $pre_x\ge s$ 的 $x$ 停止。

考虑一次跳过，为了往前进，我们必须把 $x$ 那个位置的颜色删掉一个（可以是 $x$ ，也可以是 $x$ 之前的），根据贪心，每个颜色一定是只留下最大的那一个。删除完毕后，我们就可以在 $x$ 之后找下一个 $pre_{x'}\ge s$ 的位置，以此类推做 $k$ 次就可以求出最优解。

求和可以用树状数组，找位置用线段树二分，维护 $pre$ 用set就可以了。

示例程序

#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200000,maxt=maxn<<2;

int n,te,c[maxn+5],v[maxn+5],pre[maxn+5];
set<int> S[maxn+5];set<int>::iterator L,R;
LL sum[maxn+5],ans;int MAX[maxt+5],res;
int ti,vis[maxn+5],val[maxn+5];

void Add(int x,int y) {for (;x<=n;x+=x&-x) sum[x]+=y;}
LL Sum(int x) {LL S=0;for (;x;x-=x&-x) S+=sum[x];return S;}
void Build(int l,int r,int p=1){
    if (l==r) {MAX[p]=pre[l];return;}
    int mid=l+(r-l>>1);
    Build(l,mid,p<<1);Build(mid+1,r,p<<1|1);
    MAX[p]=max(MAX[p<<1],MAX[p<<1|1]);
}
void Update(int pos,int l=1,int r=n,int p=1){
    if (l==r) {MAX[p]=pre[l];return;}
    int mid=l+(r-l>>1);
    pos<=mid?Update(pos,l,mid,p<<1):Update(pos,mid+1,r,p<<1|1);
    MAX[p]=max(MAX[p<<1],MAX[p<<1|1]);
}
void FindL(int L,int R,int k,int l=1,int r=n,int p=1){
    if (MAX[p]<k) return;
    if (L==l && r==R){
        if (l==r) {res=l;return;}
        int mid=l+(r-l>>1);
        MAX[p<<1]>=k?FindL(L,mid,k,l,mid,p<<1):FindL(mid+1,R,k,mid+1,r,p<<1|1);
        return;
    }
    int mid=l+(r-l>>1);
    if (R<=mid) FindL(L,R,k,l,mid,p<<1); else if (L>mid) FindL(L,R,k,mid+1,r,p<<1|1); else {
        FindL(L,mid,k,l,mid,p<<1);
        if (res<=n) return;
        FindL(mid+1,R,k,mid+1,r,p<<1|1);
    }
}
int main(){
    scanf("%d%d",&n,&te);
    for (int i=1;i<=n;i++) scanf("%d%d",&c[i],&v[i]),S[c[i]].insert(i);
    for (int i=1;i<=n;i++){
        L=S[c[i]].lower_bound(i);
        if (L!=S[c[i]].begin()) pre[i]=*prev(L);
    }
    for (int i=1;i<=n;i++) sum[i]=sum[i-1]+v[i];
    for (int i=n;i;i--) sum[i]-=sum[i-(i&-i)];
    Build(1,n);
    for (int t=1,tp,x,y,z;t<=te;t++){
        scanf("%d%d%d",&tp,&x,&y);
        if (tp==2){
            res=n+1;FindL(x,n,x);
            LL now=Sum(res-1)-Sum(x-1);
            ans=now;
            ti++;
            for (int i=1;i<=y && res<=n;i++){
                if (vis[c[res]]<ti) vis[c[res]]=ti,val[c[res]]=v[pre[res]];
                now-=val[c[res]];
                val[c[res]]=max(val[c[res]],v[res]);
                now+=val[c[res]];
                int lst=res;
                res=n+1;if (lst+1<=n) FindL(lst+1,n,x);
                now+=Sum(res-1)-Sum(lst);
                ans=max(ans,now);
            }
            printf("%lld\n",ans);
        } else {
            scanf("%d",&z);
            Add(x,z-v[x]);v[x]=z;
            L=S[c[x]].lower_bound(x);R=next(L);
            int lst=0;
            if (L!=S[c[x]].begin()) lst=*prev(L);
            if (R!=S[c[x]].end()) pre[*R]=lst,Update(*R);
            S[c[x]].erase(x);
            L=S[y].insert(x).first;R=next(L);
            if (L!=S[y].begin()) pre[x]=*prev(L); else pre[x]=0;
            if (R!=S[y].end()) pre[*R]=x,Update(*R);
            Update(x);c[x]=y;
        }
    }
    return 0;
}