zcmimi's blog

查看原题

点击跳转

答案与位置没有关系,把序列当作集合来看

设大于等于s的数有cnt个,小于s的数和为sum

那么sum\ge s(c-cnt)

可以用 离散化+树状数组 / 平衡树 维护

#include<bits/stdc++.h>
typedef long long ll;
const int N=1000011;
int n,nn,m,a[N],b[N],s[N];ll S[N];
struct que{int op,x,y;}q[N];
void add(int x,int v){for(int i=x;i<=nn;i+=i&-i)s[i]+=v;}
void ADD(int x,int v){for(int i=x;i<=nn;i+=i&-i)S[i]+=v;}
int ask(int x){int res=0;for(int i=x;i;i-=i&-i)res+=s[i];return res;}
ll ASK(int x){ll res=0;for(int i=x;i;i-=i&-i)res+=S[i];return res;}
int get(int x){return std::lower_bound(b+1,b+nn+1,x)-b;}
int main(){
    scanf("%d%d",&n,&m);
    char c[5];
    for(int i=1;i<=m;++i)
        scanf("%s%d%d",c,&q[i].x,&q[i].y),
        q[i].op=c[0]=='U'?0:1,
        b[i]=q[i].y;
    std::sort(b+1,b+m+1);
    nn=std::unique(b+1,b+m+1)-b-1;
    for(int i=1;i<=m;++i){
        int x=get(q[i].y),X;
        if(!q[i].op){
            if(X=a[q[i].x])add(X,-1),ADD(X,-b[X]);
            a[q[i].x]=x;
            add(x,1),ADD(x,q[i].y);
        }
        else puts((x?ASK(x-1):0)>=1ll*b[x]*(q[i].x-ask(nn)+ask(x-1))?"TAK":"NIE");
    }
}
LG 3586 [POI2015]LOG
comment评论
Search
search