题解 P4879 【ycz的妹子】

Wolfycz · 2018-09-10 09:10:19 · 题解

我的妹子当然要我写个题解啊

其实我是没有妹子的。。。

这题就是一个裸的线段树单点查询区间修改，不过好像比赛的时候好多人对题面有问题啊。。。

我现在来解释一下题面好吧

• 青梅竹马们都喜欢我（逃）
• 青梅竹马没有特权，长大之后也是妹子，会被其他妹子赶走
• 每个城市只能有一个妹子，妹子的存在不是按颜值来的，谁后来谁就可以待在那个城市
• y可以为负数，两个y都可以为负数，但是出题人忘记改下面的限制了。。。不过讲真没啥影响，开个long long可以解决一切问题
• I x y操作中y有为0的情况，所以千万不要用权值来判是否存在（不会有人用权值判的吧）
• D x y操作是指第x个妹子，不是第x个城市。。。那些有妹子的城市从编号小到大数第x个，不是指操作顺序的第x个
• 城市编号不是1~n，记住这一点

所以只有删除操作麻烦点，多几个cnt数组就好。但是如果没有删除操作就可以直接开个数列，线段树都不要了。。。

然后就贴代码吧

/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline int read(){
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar())  if (ch=='-')    f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())    x=(x<<1)+(x<<3)+ch-'0';
    return x*f;
}
inline void print(int x){
    if (x>=10)  print(x/10);
    putchar(x%10+'0');
}
const int N=1e5;
int val[(N<<1)+10];
struct Segment{
    #define ls (p<<1)
    #define rs (p<<1|1)
    struct node{
        int cnt;ll sum;
        void insert(int _sum,int _cnt){sum=_sum,cnt=_cnt;}
        node(){sum=cnt=0;}
    }tree[(N<<3)+10];
    friend node operator +(const node &x,const node &y){
        node z;
        z.sum=x.sum+y.sum;
        z.cnt=x.cnt+y.cnt;
        return z;
    }
    void build(int p,int l,int r){
        if (l==r){
            tree[p].insert(val[l],(bool)val[l]);
            return;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid),build(rs,mid+1,r);
        tree[p]=tree[ls]+tree[rs];
    }
    void change(int p,int l,int r,int x,int v){
        if (l==r){
            tree[p].insert(v,1);
            return;
        }
        int mid=(l+r)>>1;
        if (x<=mid) change(ls,l,mid,x,v);
        else    change(rs,mid+1,r,x,v);
        tree[p]=tree[ls]+tree[rs];
    }
    void insert(int p,int l,int r,int x,int v){
        if (l==r){
            tree[p].sum-=v;
            return;
        }
        int mid=(l+r)>>1;
        if (x<=mid) insert(ls,l,mid,x,v);
        else    insert(rs,mid+1,r,x,v);
        tree[p]=tree[ls]+tree[rs];
    }
    void Delete(int p,int l,int r,int x){
        if (l==r){
            tree[p].insert(0,0);
            return;
        }
        int mid=(l+r)>>1;
        if (x<=tree[ls].cnt)    Delete(ls,l,mid,x);
        else    Delete(rs,mid+1,r,x-tree[ls].cnt);
        tree[p]=tree[ls]+tree[rs];
    }
}Tree;
char s[2];
int main(){
    int n=read(),m=read();
    for (int i=1;i<=n;i++)  val[i]=read();
    Tree.build(1,1,N<<1);
    for (int i=1;i<=m;i++){
        scanf("%s",s);
        if (s[0]=='C'){
            int x=read(),y=read();
            Tree.insert(1,1,N<<1,x,y);
        }
        if (s[0]=='I'){
            int x=read(),y=read();
            Tree.change(1,1,N<<1,x,y);
        }
        if (s[0]=='D'){
            int x=read();
            Tree.Delete(1,1,N<<1,x);
        }
        if (s[0]=='Q')  printf("%lld\n",Tree.tree[1].sum);
    }
    return 0;
}