想法之後再補，先附上寫了316行的code(沒有模板)。(8200字元，破紀錄惹....)
#include <iostream> #include <stdio.h> #include <vector> #include <algorithm> #include <utility> #include <ctime> #include <cstdlib> #include <cassert> using namespace std; typedef pair<int,int> pii; const int MAX_N = 2e5+6; const int MAX_M = 4e5+6; const int INF= 1e9 + 7; #define Treap Meruru pii operator+(const pii &p1,const pii &p2) { return make_pair(min(p1.first,p2.first),max(p1.second,p2.second)); } int f(int x) { return x; } struct Kirino { int dis_mx; pii range; void shootingstars(int val) { range=make_pair(val,val); dis_mx = -INF; } }; Kirino empty=Kirino{-INF,make_pair(INF,-INF)}; Kirino operator+(Kirino k1,Kirino k2) { Kirino kirino; kirino.dis_mx = max(f(k1.dis_mx),f(k2.dis_mx )); kirino.range = k1.range + k2.range; return kirino; } struct Meruru { Meruru *lc,*rc; Kirino kirino; int sz; int val; int r; int dis; int pri; Meruru(int _val) { kirino.shootingstars(_val); lc=rc=NULL; sz=1; pri = rand(); dis=-INF; val = _val; r=-INF; } }; int Sz(Meruru* m) { return m?m->sz:0; } Kirino Kiri(Meruru* m) { return m?m->kirino:empty; } void pull(Meruru* m) { if (!m) return; m->sz = Sz(m->lc) + Sz(m->rc) + 1; m->kirino = Kiri(m->lc) + Kirino{m->dis,make_pair(m->val,m->val)} + Kiri(m->rc); } Meruru* merge(Meruru* m1,Meruru *m2) { if (!m1 || !m2) return m1?m1:m2; else if (m1->pri > m2->pri) { m1->rc=merge(m1->rc,m2); pull(m1); return m1; } else { m2->lc=merge(m1,m2->lc); pull(m2); return m2; } } void split_by_val(Meruru *m,int k,Meruru* &m1,Meruru* &m2) { if (!m) { m1=m2=NULL; return; } else if (m->val <= k) { m1=m; split_by_val(m->rc,k,m1->rc,m2); pull(m1); } else { m2=m; split_by_val(m->lc,k,m1,m2->lc); pull(m2); } } void split_by_sz(Meruru *m,int k,Meruru* &m1,Meruru* &m2) { if (!m) { m1=m2=NULL; return; } else if (Sz(m->lc) + 1 <= k) { m1=m; split_by_sz(m->rc,k-Sz(m->lc)-1,m1->rc,m2); pull(m1); } else { m2=m; split_by_sz(m->lc,k,m1,m2->lc); pull(m2); } } int c[MAX_N]; struct Q { int type,a,b,c; void input() { scanf("%d",&type); if (type==0) { scanf("%d %d",&a,&c); a++; b=a; } else { scanf("%d %d %d",&a,&b,&c); a++; } } } q[MAX_N]; Meruru* meruru[MAX_M]; void pp(Meruru* m) { if (!m) return; pp(m->lc); cout<<m->val<<' '; pp(m->rc); } void haha() { for (int i=0;6>i;i++) { cout<<"Let us see meruru["<<i<<"] : "; pp(meruru[i]); cout<<endl; } } int g(int x) { if (x>MAX_M) return -INF; else return x; } int main () { srand(time(NULL)); int n,qq,kk; scanf("%d %d %d",&n,&qq,&kk); vector<int> v; for (int i=1;n>=i;i++) { scanf("%d",&c[i]); v.push_back(c[i]); } for (int i=1;qq>=i;i++) { q[i].input(); v.push_back(q[i].c); } sort(v.begin(),v.end()); v.resize(unique(v.begin(),v.end()) - v.begin()); for (int i=1;n>=i;i++) { c[i] = lower_bound(v.begin(),v.end(),c[i]) - v.begin() + 1; // cout<<"c["<<i<<"] = "<<c[i]<<endl; } for (int i=1;qq>=i;i++) { q[i].c = lower_bound(v.begin(),v.end(),q[i].c) - v.begin() + 1; } int nn=v.size(); for (int i=1;nn>=i;i++) { meruru[i] = NULL; } for (int i=1;n>=i;i++) { int ii=c[i]; int sz=Sz(meruru[ii]); // cout<<"ii = "<<ii<<" , sz = "<<sz<<" , i = "<<i<<endl; if (sz == 0) { meruru[ii] = new Meruru(i); // cout<<"hihi i = "<<i<<endl; } else { Meruru *tl; split_by_sz(meruru[ii],sz-1,tl,meruru[ii]); meruru[ii]->r = i; meruru[ii]->dis = i-meruru[ii]->val; meruru[ii] = merge(merge(tl,meruru[ii]),new Meruru(i)); } // cout<<"i = "<<i<<endl; // haha(); // cout<<"after process ii = "<<ii<<" , sz = "<<Sz(meruru[ii])<<" , i = "<<i<<endl; } // haha(); for (int i=1;qq>=i;i++) { // cout<<"i = "<<i<<" query = "<<"("<<q[i].type<<","<<q[i].a<<","<<q[i].b<<","<<q[i].c<<")"<<endl; int type=q[i].type; if (type == 0) { int p=q[i].a; int k=q[i].c; //change int ori=c[p]; if (ori == k) continue; c[p] = k; //delete first Meruru *m1,*m2,*m3; split_by_val(meruru[ori],p-1,m1,meruru[ori]); if (Sz(m1) == 0) { // split_by_sz(meruru[ori],1,m2,meruru[ori]); split_by_val(meruru[ori],p,m2,meruru[ori]); assert(Sz(m2)==1 && m2->val == p); delete(m2); } else { split_by_sz(m1,Sz(m1)-1,m1,m2); //m2 is the last valid split_by_sz(meruru[ori],1,meruru[ori],m3); assert(Sz(meruru[ori])==1 && meruru[ori]->val == p); m2->r = meruru[ori]->r; m2->dis = m2->r-m2->val; delete(meruru[ori]); // pull(m3); // m2->r = g((Kiri(m3)).range.first); // m2->dis = f(m2->r-m2->val); pull(m2); meruru[ori] = merge(m1,merge(m2,m3)); } // cout<<"finish deleting !!!"<<endl; //Ooosh... delete finished //now let's adding Meruru *m4,*m5,*m6; if (Sz(meruru[k]) == 0) { // cout<<"inn"<<endl; meruru[k] = new Meruru(p); } else { split_by_val(meruru[k],p-1,m4,meruru[k]); if (Sz(m4)==0) { // cout<<"haha"<<endl; m5 = new Meruru(p); pull(meruru[k]); m5->r = g(Kiri(meruru[k]).range.first); if (m5->r == INF) m5->r=-INF; m5->dis = m5->r - m5->val; pull(m5); meruru[k] = merge(m5,meruru[k]); } else { // cout<<"hehe"<<endl; split_by_sz(m4,Sz(m4)-1,m4,m5); m6 = new Meruru(p); m6->r=m5->r; m6->dis = m6->r-m6->val; m5->r=p; m5->dis = f(m5->r - m5->val ); // cout<<"still_in"<<endl; // pull(meruru[k]); // m6->r = g(Kiri(meruru[k]).range.first); // m6->dis = f(m6->r - m6->val ); pull(m5); pull(m6); meruru[k] = merge(merge(m4,m5),merge(m6,meruru[k])); } } } else { // cout<<"i = "<<i<<" : "; // pp(meruru[q[i].c ]); // cout<<endl; int l=q[i].a,r=q[i].b,c=q[i].c; if (Sz(meruru[c]) == 0) { printf("%d\n",r-l+1); } else { Meruru *m1,*m2,*m3; split_by_val(meruru[c],l-1,m1,m2); split_by_val(m2,r,m2,m3); if (Sz(m2) == 0 ){ printf("%d\n",r-l+1); } else if (Sz(m2) == 1) { int val = m2->val; printf("%d\n",max(val-l,r-val)); } else { Meruru* m4; split_by_sz(m2,Sz(m2)-1,m2,m4); int ans_mx = m2->kirino.dis_mx-1; pull(m2); ans_mx = max(ans_mx,max(f(m2->kirino.range.first-l),f(r-m4->val) ) ); m2 = merge(m2,m4); printf("%d\n",ans_mx); } meruru[c] = merge(merge(m1,m2),m3); } } // cout<<"i = "<<i<<endl; // haha(); } }
沒有留言:
張貼留言