话说ycz是哪个神犇，为什么他会有很多很多的妹子？

题目背景

ycz有很多很多的妹子（ycz：瞎说）

题目描述

机房神犇ycz有n个青梅竹马，她们分别住在1~n号城市中。小时候的她们美丽可爱，但是由于女大十八变，有些妹子的颜值发生了变化，但是十分重感情的ycz神犇不忍心抛弃她们，于是记录下来了她们颜值变化的值，我们用C, x, y表示第x个城市的妹子的颜值下降了y。长大之后的ycz非常有魅力，有许多妹子被ycz迷得神魂颠倒，我们用I, x, y表示第x个城市有一个妹子喜欢上了ycz，她的颜值为y（y有可能是负数，但是ycz来者不拒）。但在中途有一些妹子和ycz吵架了，于是就分手了，我们用D, x表示第x个妹子和ycz分手了。

最近神犇ycz要去全国各地找他的妹子们，为了方便计算，我们珂以把ycz的妹子所在的城市当作是一条直线，并且挨在一起。神犇ycz由于忙于和他的妹子们联系此时已经很累了，于是交给你一个这样的任务：他想知道他在某个时间去找他的所有妹子们珂以获得多大的愉悦度，这个愉悦度为他找的妹子的颜值数，你要做的就是求出这个愉悦度之和（注意长大后妹子们的颜值可能为负数/滑稽）。

注意：每个城市只允许有一个妹子，也就是说后来喜欢上ycz的妹子会赶走之前这个城市喜欢ycz的妹子~~（一城不容二女）~~。

UPD:

青梅竹马都是喜欢ycz的。

分手的第x个妹子不是第x城市的妹子，是指从前往后数第x个有妹子的城市的妹子

青梅竹马长大后就是妹子

修改的值y不为负数，但是颜值减去之后可能为负数

原题链接

Slove

其实这就是一个需要稍加变化的线段树。

操作说明：

C 单点修改

I 同样是单点修改，但是需要一点变化

D 还是单点修改，也需要一点变化（tip:这里的x指的不是第x个城市，而是从前往后第x个，两者还是有区别的）

Q 区间查询，其实就是线段树里的节点一

code

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=2000001;
long long n,m;
struct note{
    long long l,r,w,cnt;   //l表左端点，r表右端点，w表颜值总和，cnt表妹子数（tip:这个cnt是很重要的）
}d[maxn];
long long a[maxn];   // tip:颜值的值一定要开longlong,包括上面的w;
char c;
int x,y;
void build(int k,int s,int t){   //建树
    d[k].l=s;
    d[k].r=t;
    if(s==t){
        d[k].w=a[s];
        if(a[s]>0) d[k].cnt=1;
        return ;
    }
    else{
        build(k*2,s,(s+t)/2);
        build(k*2+1,(s+t)/2+1,t);
        d[k].w=d[k*2].w+d[k*2+1].w;
        d[k].cnt=d[k*2].cnt+d[k*2+1].cnt;
    }
}
void sub(int k){   //普通的单点修改
    if(d[k].l==d[k].r){
        d[k].w-=y;
        return ;
    }
    int mid=(d[k].l+d[k].r)/2;
    if(x<=mid) sub(k*2);
    else sub(k*2+1);
    d[k].w=d[k*2].w+d[k*2+1].w;
}
void revise(int k){   //还是普通的单点修改
    if(d[k].l==d[k].r){
         d[k].w=y;
         d[k].cnt=1;   //cnt=1,这样的话不管之前这个城市有没有妹子，都可以正确表示
         return ;
    }
    int mid=(d[k].l+d[k].r)/2;
    if(x<=mid) revise(k*2);
    else revise(k*2+1);
    d[k].w=d[k*2].w+d[k*2+1].w;
    d[k].cnt=d[k*2].cnt+d[k*2+1].cnt;
}
void leave(int k){  //本题最难处理的部分
    if(d[k].l==d[k].r){
        d[k].w=0;
        d[k].cnt=0;
        return ;
    }
    if(x<=d[k*2].cnt) leave(k*2); //如果左子树的妹子数大于x,就向左子树寻找     
    else{   //如果左子树的妹子数小于x,就向右子树寻找（tip:为什么x还要减去左子树的妹子数呢？想一想）
        x-=d[k*2].cnt；
        leave(k*2+1)；
    }
    d[k].cnt=d[k*2].cnt+d[k*2+1].cnt;
    d[k].w=d[k*2].w+d[k*2+1].w;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,500000);
    for(int i=1;i<=m;i++){
        cin>>c;
        if(c=='C'){
            cin>>x>>y;
            sub(1);
        }
        else if(c=='I'){
            cin>>x>>y;
            revise(1);
        }
        else if(c=='D'){
            cin>>x;
            leave(1);
        }
        else if(c=='Q') cout<<d[1].w<<endl；
    }
    return 0;
}

自认为简洁的代码