本文主要是介绍#线段树，树状数组#洛谷 4879 ycz的妹子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
分析（线段树）
首先，要维护区间颜值和以及区间妹子个数，其实最难的应该是删除，在找的时候运用区间妹子个数，但是好像非正解，因为应该容易被HACK掉
代码（线段树）
#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
typedef long long ll;
const int N=200001;
int cnt[N<<2],n,m; ll w[N<<2];
inline signed iut(){rr int ans=0,f=1; rr char c=getchar();while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans*f;
}
inline void print(ll ans){if (ans>9) print(ans/10);putchar(ans%10+48);
}
void build(int k,int l,int r){if (l==r){if (l<=n) w[k]=iut(),++cnt[k];return;}rr int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);w[k]=w[k<<1]+w[k<<1|1],cnt[k]=cnt[k<<1]+cnt[k<<1|1];
}
void upd1(int k,int l,int r,int x,int y,int t){if (l==r){if (!t) w[k]-=y;else w[k]=y,cnt[k]=1;return;}rr int mid=(l+r)>>1;if (x<=mid) upd1(k<<1,l,mid,x,y,t);else upd1(k<<1|1,mid+1,r,x,y,t);w[k]=w[k<<1]+w[k<<1|1],cnt[k]=cnt[k<<1]+cnt[k<<1|1];
}
inline void upd2(int k,int l,int r,int x){if (l==r){if (x==cnt[k]) w[k]=0,--cnt[k];return;}rr int mid=(l+r)>>1;if (x<=cnt[k<<1]) upd2(k<<1,l,mid,x);else upd2(k<<1|1,mid+1,r,x-cnt[k<<1]);w[k]=w[k<<1]+w[k<<1|1];cnt[k]=cnt[k<<1]+cnt[k<<1|1];
}
signed main(){n=iut(); m=iut();build(1,1,N^1); rr char q='#';while (m--){ getchar(); if (q=='Q') getchar(); q=getchar();rr int x; if (q!='Q') x=iut();if (q=='C') upd1(1,1,N^1,x,iut(),0);else if (q=='I') upd1(1,1,N^1,x,iut(),1);else if (q=='D') upd2(1,1,N^1,x);else if (q=='Q') print(w[1]),putchar(10);}return 0;
}
分析（树状数组）
那么直接用城市个数，树状数组记录妹子个数，分析树状数组的性质，在删除的时候采用试填法，用二进制填进去，找到答案，但是由于不一定存在，所以要改一下下
代码
#include <cstdio>
#include <cctype>
#define rr register
using namespace std;
typedef long long ll;
const int N=500000; bool v[N+1];
int c[N+1],n,m; ll a[N+1];
inline signed iut(){rr int ans=0,f=1; rr char c=getchar();while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans*f;
}
inline void print(ll ans){if (ans>9) print(ans/10);putchar(ans%10+48);
}
inline void add(int x,int y){while (x<=N) c[x]+=y,x+=-x&x;
}
inline signed answ(int x){rr int bas=1,ans=0,sum=0;for (;bas<=N&&c[bas]<=x;bas<<=1);for (bas>>=1;bas;bas>>=1)if ((ans|bas)<=N&&sum+c[ans|bas]<x)ans|=bas,sum+=c[ans|bas];return ans+1;
}
signed main(){n=iut(); m=iut(); rr ll sum=0; rr char q='#';for (rr int i=1;i<=n;++i) a[i]=iut(),sum+=a[i],v[i]=c[i]=1;for (rr int i=2;i<=N;++i) c[i]+=c[i-1];for (rr int i=N;i;--i) c[i]-=c[i-(-i&i)];while (m--){rr int x,y; getchar();if (q=='Q') getchar();q=getchar(); if (q!='Q') x=iut();if (q=='C') y=iut(),a[x]-=y,sum-=y;else if (q=='I'){y=iut();sum+=y-a[x],a[x]=y;if (!v[x]) v[x]=1,add(x,1);}else if (q=='Q') print(sum),putchar(10);else sum-=a[x=answ(x)],v[x]=a[x]=0,add(x,-1);}return 0;
}
这篇关于#线段树，树状数组#洛谷 4879 ycz的妹子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
