题解 P4879 【ycz的妹子】

· · 题解

我深感Wolfycz的代码写的太漂(chou)亮(lou)了，因此我决定我也要来发一篇博客...

这题70分的话，只需要暴力就好了....

然后那个30的做法...暴力分真的虾捷豹给的...

这个是暴力代码...

code:

/*Program from Luvwgyx*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
int n,m,a[maxn];char s[10];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=m;i++){
        scanf("%s",s+1);
        if(s[1]=='C'){
            int x=read(),y=read();
            a[x]-=y;
        }
        if(s[1]=='I'){
            int x=read(),y=read();
            a[x]=y;
        }
        if(s[1]=='D'){
            int cnt=0,pos,x=read();
            for(int i=1;i<=maxn-10;i++)
                if(a[i]){cnt++;if(cnt==x){pos=i;break;}}
            a[pos]=0;
        }
        if(s[1]=='Q'){
            int ans=0;
            for(int i=1;i<=maxn-10;i++)
                ans+=a[i];
            printf("%d\n",ans);
        }
    }
    return 0;
}

然后100分的做法的话，其实线段树就好了...

这题题面是我给的(Wolfycz改的)，你们要骂就骂我(他)吧...(虽然我个人觉得没啥问题...)

这题大家珂能因为我说是签到题的原因，没仔细看题...

我之前的描述是第x个城市的妹子，而后面D\ x这个操作，我的描述是第x个妹子，大家竟然没发现不对劲.../汗

然后其实我们用线段树存下来区间和以及这个区间内妹子的个数，然后单点修改区间查询就好了...

注意：delete的时候要注意，判断是走左边还是走右边的时候，不能通过和mid的比较来判断，而是应该与存着的妹子的个数tree[mid].cnt比较来判断...然后...应该就没啥要注意的了...

code:

/*Program from Luvwgyx*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll maxn=2e5+10;
ll n,m,a[maxn];char s[10];
struct node{ll cnt,sum;}tree[maxn<<2];
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void update(ll k){
    tree[k].cnt=tree[k<<1].cnt+tree[k<<1|1].cnt;
    tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum;
    return;
}
void build(ll k,ll l,ll r){
    if(l==r){
        tree[k].sum=a[l];
        if(a[l]!=0)tree[k].cnt++;
        return ;
    }
    ll mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    update(k);
}
void change(ll k,ll l,ll r,ll x,ll y){
    if(l==r){tree[k].sum-=y;/*prllf("\n%d\n",l);*/return ;}
    ll mid=(l+r)>>1;
    if(x<=mid)change(k<<1,l,mid,x,y);
    else change(k<<1|1,mid+1,r,x,y);
    update(k);
}
void add(ll k,ll l,ll r,ll x,ll y){
    if(l==r){tree[k].sum=y;tree[k].cnt=1;/*prllf("\n%d\n",l);*/return ;}
    ll mid=(l+r)>>1;
    if(x<=mid)add(k<<1,l,mid,x,y);
    else add(k<<1|1,mid+1,r,x,y);
    update(k);
}
void del(ll k,ll l,ll r,ll x){
    if(l>r)return ;//prllf("%d %d\n",l,r);
    if(l==r&&x==tree[k].cnt){tree[k].sum=0;tree[k].cnt--;return ;}
    ll mid=(l+r)>>1;//prllf("%d\n",tree[k<<1].cnt);
    if(x<=tree[k<<1].cnt)del(k<<1,l,mid,x);
    else del(k<<1|1,mid+1,r,x-tree[k<<1].cnt);
    update(k);
}
/*
void dfs(ll k,ll l,ll r){
    if(l==r){if(tree[k].sum!=0)prllf("%d:%d ",l,tree[k].sum);return ;}
    ll mid=(l+r)>>1;
    dfs(k<<1,l,mid);dfs(k<<1|1,mid+1,r);
}
*/
int main(){
    //freopen("girl10.in","r",stdin);
    //freopen("girl10.out","w",stdout);
    n=read();m=read();
    for(ll i=1;i<=n;i++)a[i]=read();
    build(1,1,maxn-10);
    while(m--){
        scanf("%s",s);
        if(s[0]=='C'){ll x=read(),y=read();change(1,1,maxn-10,x,y);}
        if(s[0]=='I'){ll x=read(),y=read();add(1,1,maxn-10,x,y);}
        if(s[0]=='D'){ll x=read();del(1,1,maxn-10,x);}
        if(s[0]=='Q')printf("%lld\n",tree[1].sum);
        //dfs(1,1,maxn-10);puts("");
    }
    return 0;
}