题解 P4879 【ycz的妹子】

当初比赛时候用了map，成功拿到暴力分。 其实这道题拿来练习非常不错，~~其实啥东西都能往上套~~ 可以把所有【有妹子的】城市的【编号】看成一个序列，第x个妹子就是序列第k大。 那么我们只要求出动态整体第k大就好了。 ~~所以怼一颗支持rank的平衡树。（变量可读性应该不错【为不加注释找借口】）~~ ```cpp #include <cstdio> #include <vector> #include <stack> #ifndef nullptr #define nullptr NULL #endif // ! nullptr using namespace std; inline int max(int a, int b) { return a > b ? a : b; } inline int min(int a, int b) { return a < b ? a : b; } enum sonptr { ls = 0, rs = 1 }; class node { public: int size; int v; //bool erased; node* son[2]; node(int _v = 0) :v(_v), size(1) { son[ls] = son[rs] = nullptr; }; inline void update() { size = 1; if (son[ls]) { size += son[ls]->size; } if (son[rs]) { size += son[rs]->size; } } inline void clear() { v = 0; size = 1; son[ls] = son[rs] = nullptr; } inline int ls_size()const { return son[ls] ? son[ls]->size : 0; } }; const int kmaxn = 500000 + 5; node mempool[kmaxn]; stack<node*> garbage_collector; int mpt; node* malloc_node(int v) { node* t = nullptr; if (!garbage_collector.empty()) { t = garbage_collector.top(); garbage_collector.pop(); t->clear(); t->v = v; } else if (mpt >= kmaxn) t = new node(v); else { t = &mempool[mpt++]; t->v = v; } return t; } inline void free_node(node*& p) { garbage_collector.push(p); } class balance_tree { balance_tree(balance_tree&); public: double alpha; node* root; vector<node*> vec; balance_tree(double _alpha = 0.75) :alpha(_alpha), root(nullptr) {} inline const bool bad(node* p)const { return max(p->ls_size(), p->son[rs] ? p->son[rs]->size : 0) > p->size*alpha; } node** basic_insert(int v, node*& p); void insert(int v); void travel(node* p); node* rebuild(int l, int r); bool basic_erase(int v, node*& p);//true means erased inline bool erase(int v); int get_rank(int v); int get_value_by_rank(int k); int upper_bound(int v); int lower_bound(int v); }; node** balance_tree::basic_insert(int v, node*& p) { if (!p) { p = malloc_node(v); return nullptr; } ++p->size; node** t = basic_insert(v, p->son[(v >= p->v)]); if (bad(p)) t = &p; return t; } void balance_tree::insert(int v) { node** t = basic_insert(v, root); if (t) { vec.clear(); vec.reserve((*t)->size + 5); travel(*t); *t = rebuild(0, vec.size()); } } void balance_tree::travel(node* p) { if (!p) return; travel(p->son[ls]); vec.push_back(p); travel(p->son[rs]); } node* balance_tree::rebuild(int l, int r) { if (l >= r) return nullptr; int mid = (l + r) >> 1; node* t = vec[mid]; t->son[ls] = rebuild(l, mid); t->son[rs] = rebuild(mid + 1, r); t->update(); return t; } bool balance_tree::basic_erase(int v, node*& p) { if (p->v == v) { if (!(p->son[ls] && p->son[rs])) { free_node(p); p = p->son[bool(p->son[rs])]; //return true; } else { --p->size; bool c = p->ls_size() < (p->son[rs] ? p->son[rs]->size : 0); node** t = &(p->son[c]); c = !c; while ((*t)->son[c]) { --(*t)->size; t = &(*t)->son[c]; } p->v = (*t)->v; free_node(*t); *t = (*t)->son[!c]; } return true; } if (basic_erase(v, p->son[v > p->v])) { --p->size; return true; } else return false; } inline bool balance_tree::erase(int v) { return basic_erase(v, root); } int balance_tree::get_rank(int v) { int rk = 0; node* p = root; while (p) { if (v > p->v) { rk += p->ls_size() + 1; p = p->son[rs]; } else p = p->son[ls]; } return rk + 1; } int balance_tree::get_value_by_rank(int k) { int rk = 0; node* p = root; while (p) { if (rk + p->ls_size() + 1 < k) { rk += p->ls_size() + 1; p = p->son[rs]; } else if (rk + p->ls_size() >= k) { p = p->son[ls]; } else { return p->v; } } return 0; } int balance_tree::upper_bound(int v) { return get_value_by_rank(get_rank(v + 1)); } int balance_tree::lower_bound(int v) { //cout << get_rank(v) << endl; return get_value_by_rank(get_rank(v) - 1); } #define reg register int n,m; balance_tree sbt; long long data[kmaxn]; long long maxjoy; bool exist[kmaxn]; inline void read(int& i) { scanf("%d",&i); } inline void readchar(char& ch) { do { ch=getchar(); }while(ch=='\n'||ch=='\r'||ch==' '); } void leave(int x) { int pos=sbt.get_value_by_rank(x); maxjoy-=data[pos]; data[pos]=0; sbt.erase(pos); exist[pos]=false; } int main() { read(n); read(m); for(reg int i=1;i<=n;++i) { //cin>>data[i]; scanf("%lld",&data[i]); maxjoy+=data[i]; exist[i]=true; sbt.insert(i); } reg char opt; reg int x,y; ++m; while(--m) { //cin>>opt; readchar(opt); switch(opt) { case 'C': //cin>>x>>y; read(x); read(y); maxjoy-=y; data[x]-=y; break; case 'I': //cin>>x>>y; read(x); read(y); if(exist[x]) maxjoy-=data[x]; else{ exist[x]=true; sbt.insert(x); } data[x]=y; maxjoy+=y; break; case 'D': //cin>>x; read(x); leave(x); break; case 'Q': //cout<<maxjoy<<endl; printf("%lld\n",maxjoy); break; } } return 0; } ``` ~~跑的没有分块快~~ 补充一个分块的代码，应该还算简洁。 ```cpp // luogu-judger-enable-o2 #include <cstdio> #include <cmath> #define reg register using namespace std; const int kmaxn=500000+25; long long data[kmaxn]; bool exist[kmaxn]; int block[kmaxn]; int belong[kmaxn]; int n,m; int block_num,block_size; long long maxjoy=0; inline void leave(const int& x) { reg int rk=0; for(reg int i=1;i<=block_num+10;++i) { if(rk+block[i]>=x)//find { --block[i]; i=block_size*(i-1)+1;//begin pos for(;rk<x;++i) { if(exist[i]) ++rk; } --i; maxjoy-=data[i]; data[i]=0; exist[i]=false; return; } else rk+=block[i]; } } inline void read(int& i) { scanf("%d",&i); } inline void readchar(char& ch) { do { ch=getchar(); }while(ch=='\n'||ch=='\r'||ch==' '); } int main() { read(n); read(m); //block_size=5; block_size=sqrt(kmaxn-1); block_num=(kmaxn-1)/block_size+bool((kmaxn-1)%block_size); for(reg int i=1;i<=n;++i) { //cin>>data[i]; scanf("%lld",&data[i]); maxjoy+=data[i]; exist[i]=true; } for(reg int i=1,j=1;i<kmaxn;++i) { if(i>j*block_size) ++j; belong[i]=j; block[j]+=exist[i]; } reg char opt; reg int x,y; while(m--) { //cin>>opt; readchar(opt); switch(opt) { case 'C': //cin>>x>>y; read(x); read(y); maxjoy-=y; data[x]-=y; break; case 'I': //cin>>x>>y; read(x); read(y); if(exist[x]) { maxjoy-=data[x]; --block[belong[x]]; } exist[x]=true; data[x]=y; maxjoy+=y; ++block[belong[x]]; break; case 'D': //cin>>x; read(x); leave(x); break; case 'Q': //cout<<maxjoy<<endl; printf("%lld\n",maxjoy); break; } } return 0; } ``` ~~线段树做法写的早，代码难看就不发了~~