题目大意

给定一个全0序列,两种操作:修改一个位置的数字,查询能否连续S次对序列中的C个正数减一。

题解

对于查询操作,如果一个数字的值大于S,那么每次的选择序列中都可以加入这个数字,他的意义是让C-=1,如果数字小于S,那么它可以贡献等于其数值的减一次数。

所以使用树状数组分别统计数字和和数字出现次数即可。

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#define LL long long
using namespace std;

const int Maxn=1e6+50;

LL sum[Maxn+5],cnt[Maxn+5];
inline int lowbit(int x){return x&-x;}
inline void add(LL sum[],int x,LL val){
    for (int i=x;i<=Maxn;i+=lowbit(i)) sum[i]+=val;
}
inline LL get(LL sum[],int x){
    LL ret=0;
    for (int i=x;i;i-=lowbit(i)) ret+=sum[i];
    return ret;
}

struct Query{
    char op[5];
    int x,y;
}qey[Maxn+5];

int num[Maxn+5],tot;
int val[Maxn+5];

int getPosition(int val){return lower_bound(num+1,num+tot,val)-num;}

int n,m;
int main(){
    //freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) scanf("%s%d%d",qey[i].op,&qey[i].x,&qey[i].y);
    num[tot=1]=0; for (int i=1;i<=m;i++) num[++tot]=qey[i].y;
    for (int i=1;i<=n;i++) val[i]=0;

    sort(num+1,num+tot+1);
    tot=unique(num+1,num+tot+1)-num;
    //for (int i=1;i<tot;i++) printf("%d\n",num[i]);

    add(cnt,getPosition(0),n);

    for (int i=1;i<=m;i++){
        if (qey[i].op[0]=='U'){
            int idx=qey[i].x,ops=qey[i].y;
            add(cnt,getPosition(val[idx]),-1);
            add(sum,getPosition(val[idx]),-val[idx]);
            add(cnt,getPosition(ops),1);
            add(sum,getPosition(ops),ops);
            val[idx]=ops;
        }else{
            int ops=qey[i].y,lim=qey[i].x;
            lim-=get(cnt,tot)-get(cnt,getPosition(ops)-1);
            if (get(sum,getPosition(ops)-1)>=(LL)lim*ops) printf("TAK\n"); else printf("NIE\n");
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注