树状数组【洛谷P3586】 [POI2015]LOG

P3586 [POI2015]LOG

维护一个长度为n的序列，一开始都是0，支持以下两种操作：1.U k a 将序列中第k个数修改为a。2.Z c s 在这个序列上，每次选出c个正数，并将它们都减去1，询问能否进行s次操作。每次询问独立，即每次询问不会对序列进行修改。

离散化按照权值建立树状数组。

那么对于大于s的值，可以直接减去s，这一部分的贡献为\(c*(query_{geshu}(tot)-query_{geshu}(s-1))\)。

剩下的数，我们只知道他们小于s，但是不知道确切的值所以并不能用上述方法求出贡献。

但是我们知道每个数的大小，那么可以求出每个数的权值*个数之和，这些是可以作为贡献的。

也就是\(query_{quanzhi}(s-1)\)。

注意离散化。

对于离散化，一定注意当前的值要用离散化之后的还是之前的。

之后的用\(lowerbound\)求出，之后的再用求出的序号带入到离散化数组就可以。

code：

#include <iostream>
#include <cstdio>
#include <algorithm>


#define int long long

using namespace std;

const int wx=3000017;

inline int read(){
    int sum=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}
    return sum*f;
}

int a[wx],sum_geshu[wx],sum_quanzhi[wx],b[wx];
int n,m,tot;
int c[wx];
char opt[7];

struct node{
    int flag,num,to;
    int c,s;
}t[wx];

void add1(int pos,int k){
    for(int i=pos;i<=tot;i+=(i&-i))
        sum_geshu[i]+=k;
}

int query1(int pos){
    int re=0;
    for(int i=pos;i>=1;i-=(i&-i))
        re+=sum_geshu[i];
    return re;
}

void add2(int pos,int k){
    for(int i=pos;i<=tot;i+=(i&-i))
        sum_quanzhi[i]+=k;
}

int query2(int pos){
    int re=0;
    for(int i=pos;i>=1;i-=(i&-i))
        re+=sum_quanzhi[i];
    return re;
}



signed main(){
    n=read(); m=read();
    for(int i=1;i<=m;i++){
        scanf("%s",opt+1);
        if(opt[1]=='U'){
            t[i].flag=1;
            t[i].num=read();
            t[i].to=read();
            b[++tot]=t[i].to;
        }
        else{
            t[i].c=read();
            t[i].s=read();
            b[++tot]=t[i].s;
        }
    }
    sort(b+1,b+1+tot); 
    for(int i=1;i<=m;i++){
        if(t[i].flag){
            int tmp=lower_bound(b+1,b+1+tot,t[i].to)-b;
            if(a[t[i].num]){
                add1(a[t[i].num],-1);add2(a[t[i].num],-b[a[t[i].num]]);
            } 
            
            if(tmp){
                add1(tmp,1); a[t[i].num]=tmp; add2(tmp,b[tmp]);
            }
        }
        else{
            int s=lower_bound(b+1,b+1+tot,t[i].s)-b;
            int tmp=b[s]*(t[i].c-(query1(tot)-query1(s-1)));
            if(tmp<=query2(s-1))puts("TAK");
            else puts("NIE");
        }
    }
    return 0;
}

树状数组【洛谷P3586】 [POI2015]LOG

原文：https://www.cnblogs.com/wangxiaodai/p/9890822.html