测试数据1~9： 首先测试数据1-4的做法是显然的，此处不再赘述。我们关注测试数据5-7。鉴于 int len(){return r-l+1;} seg(){} seg(pair<int,pair<int,int> > p):l(p.first),r(p.second.first),x(p.second.second){} const int MAXM=1e5+10; map<int,pair<int,int> > st; int cnt[MAXM]; //操作1：请注意这不是最优代码，实际上会导致相邻两段的x相同而不合并他们的问题 void modify(int l,int r,int x){ auto it=st.upper_bound(l);--it; seg last(*it); while(it!=st.end()){ st.erase(it);cnt[last.x]-=(last.r-last.l+1); if(last.l<l){ st[last.l]={l-1,last.x}; cnt[last.x]+=(l-last.l); if(last.r>r){ st[r+1]={last.r,last.x}; cnt[last.x]+=(last.r-r); break; it=st.upper_bound(l);seg=node(*it); st[l]={r,x};cnt[x]+=(r-l+1); //操作2 void alter(int x,int w){ for(auto it=st.begin();it!=st.end();++it){ if(it->second.second==x) it->second.second=w; cnt[w]+=cnt[x];cnt[x]=0; //操作3 void exchange(int x,int y){ for(auto it=st.begin();it!=st.end();++it){ if(it->second.second==x) it->second.second=y; else if(it->second.second==y) it->second.second=x; swap(cnt[x],cnt[y]); int main() { ios::sync_with_stdio(false); int n,m,q,op,l,r,x,w,y; cin>>n>>m>>q;st[1]={n,0};cnt[0]=n; while(q--){ cin>>op; if(op==1) { cin>>l>>r>>x; modify(l,r,x); }else if(op==2){ cin>>x>>w; alter(x,w); }else if(op==3){ cin>>x>>y; exchange(x,y); }else if(op==4){ cin>>w; cout<<cnt[w]<<endl; }else{//op==5 int maxv=cnt[1],wk=1; for(int i=2;i<=m;++i){ if(cnt[i]>maxv) maxv=cnt[i],wk=i; if(cnt[0]==n) wk=0; cout<<wk<<endl; return 0;

尽管上述代码中并未特别考虑数据8~9，但由于 vector<node*> ptr; void __build(node* rt,int l,int r){ rt->l=l;rt->r=r;rt->mx=0;rt->mxpos=l; if(l==r) { ptr[l]=rt; rt->lc=rt->rc=NULL; return; int m=l+r>>1; rt->lc=new node(rt);rt->rc=new node(rt); __build(rt->lc,l,m); __build(rt->rc,m+1,r); void __upd(node *p,int val){ p->mx=val;int i=p->l; while(p->fa!=NULL){ node* ac=(p==p->fa->lc)?p->fa->rc:p->fa->lc; if(ac==NULL || p->mx>ac->mx) p->fa->mx=p->mx,p->fa->mxpos=p->mxpos; else if(p->mx==ac->mx) p->fa->mx=p->mx,p->fa->mxpos=min(p->mxpos,ac->mxpos); else p->fa->mx=ac->mx,p->fa->mxpos=ac->mxpos; p=p->fa; public: void init(int n){ v.resize(n+1,0); ptr.resize(n+1,NULL); rt=new node(NULL); __build(rt,1,n); void update(int i){ if(i>0) __upd(ptr[i],v[i]); int& operator[](int i) {return v[i];} int maxpos(){ if(rt->mx>0) return rt->mxpos; return 0; }cnt; struct seg{ int l,r,x; int len(){return r-l+1;} seg(){} seg(pair<int,pair<int,int> > p):l(p.first),r(p.second.first),x(p.second.second){} map<int,pair<int,int> > st; void modify(int l,int r,int x){ auto it=st.upper_bound(l);--it; seg last(*it); while(it!=st.end()){ st.erase(it);cnt[last.x]-=(last.r-last.l+1); if(last.l<l){ st[last.l]={l-1,last.x}; cnt[last.x]+=(l-last.l); cnt.update(last.x); if(last.r>r){ st[r+1]={last.r,last.x}; cnt[last.x]+=(last.r-r); cnt.update(last.x); break; it=st.upper_bound(l);last=seg(*it); st[l]={r,x};cnt[x]+=(r-l+1);cnt.update(x); void alter(int x,int w){ for(auto it=st.begin();it!=st.end();++it){ if(it->second.second==x) it->second.second=w; cnt[w]+=cnt[x];cnt[x]=0; cnt.update(x);cnt.update(w); void exchange(int x,int y){ for(auto it=st.begin();it!=st.end();++it){ if(it->second.second==x) it->second.second=y; else if(it->second.second==y) it->second.second=x; swap(cnt[x],cnt[y]); cnt.update(x);cnt.update(y); int main() { ios::sync_with_stdio(false); int q,op,l,r,x,w,y; cin>>n>>m>>q; cnt.init(m);cnt[0]=n; st[1]={n,0}; while(q--){ cin>>op; if(op==1) { cin>>l>>r>>x; modify(l,r,x); }else if(op==2){ cin>>x>>w; alter(x,w); }else if(op==3){ cin>>x>>y; exchange(x,y); }else if(op==4){ cin>>w; cout<<cnt[w]<<endl; }else{//op==5 cout<<cnt.maxpos()<<endl; return 0;

完整解答： 在上一解决方案的基础上，我们容易发现性能瓶颈在于操作2和操作3，它们每次都会修改所有投票段。我们不妨定义作品的“编号”和“虚拟编号”的概念。开始时，所有的编号和虚拟编号都相同。我们的操作1~5中输入的都是“虚拟编号”，因此输入时将“虚拟编号”先变回“编号”。当操作2发生时，我们记虚拟编号 int n; vector<int> fa,mp,rmp; //fa:每个点属于的集合; mp:虚拟id(1~n)到 真实id(1~n+q)的映射; rmp:真实id(1~n+q)到虚拟id的映射 int find(int x){ return x!=fa[x]?(fa[x]=find(fa[x])):x; public: void init(int n){ this->n=n;fa.resize(n+1);mp.resize(n+1);rmp.resize(n+1); for(int i=0;i<=n;++i)fa[i]=i,mp[i]=i,rmp[i]=i; int operator[](int x){return mp[x];}//将虚拟编号映射为实际编号 int map_back(int x){return rmp[find(x)];}//将实际编号映射为虚拟编号 void exchange(int u,int v){ swap(rmp[mp[u]],rmp[mp[v]]);//交换虚拟id swap(mp[u],mp[v]);//交换真实id void merge(int v,int u){ fa[find(mp[v])]=find(mp[u]);//合并v的真实id到u的真实id rmp[mp[v]]=-1; fa.push_back(++n);//为v创建新的真实id rmp.push_back(v);mp[v]=n; }uf; //线段树节点 struct node{ int l,r,mx,mxpos; node *lc,*rc,*fa; node(node* f):fa(f){} //线段树 class seg_tree{ node *rt; vector<int> v; vector<node*> ptr; void __build(node* rt,int l,int r){ rt->l=l;rt->r=r;rt->mx=0;rt->mxpos=l; if(l==r) { ptr[l]=rt; rt->lc=rt->rc=NULL; return; int m=l+r>>1; rt->lc=new node(rt);rt->rc=new node(rt); __build(rt->lc,l,m); __build(rt->rc,m+1,r); void __upd(node *p,int val){ p->mx=val;int i=p->l; while(p->fa!=NULL){ node* ac=(p==p->fa->lc)?p->fa->rc:p->fa->lc; if(ac==NULL || p->mx>ac->mx) p->fa->mx=p->mx,p->fa->mxpos=p->mxpos; else if(p->mx==ac->mx) p->fa->mx=p->mx,p->fa->mxpos=min(p->mxpos,ac->mxpos); else p->fa->mx=ac->mx,p->fa->mxpos=ac->mxpos; p=p->fa; public: void init(int n){ v.resize(n+1,0); ptr.resize(n+1,NULL); rt=new node(NULL); __build(rt,1,n); void update(int i){ if(i>0) __upd(ptr[i],v[i]); int& operator[](int i) {return v[i];} int maxpos(){ if(rt->mx>0) return rt->mxpos; return 0; }cnt; struct seg{ int l,r,x; int len(){return r-l+1;} seg(){} seg(pair<int,pair<int,int> > p):l(p.first),r(p.second.first),x(p.second.second){} map<int,pair<int,int> > st; void modify(int l,int r,int tx){ int x=uf[tx];//获取tx的真实id auto it=st.upper_bound(l);--it; seg last(*it); while(it!=st.end()){ int mb_lastx=uf.map_back(last.x); st.erase(it);cnt[mb_lastx]-=(last.r-last.l+1); if(last.l<l){ st[last.l]={l-1,last.x}; cnt[mb_lastx]+=(l-last.l); cnt.update(mb_lastx); if(last.r>r){ st[r+1]={last.r,last.x}; cnt[mb_lastx]+=(last.r-r); cnt.update(mb_lastx); break; it=st.upper_bound(l);last=seg(*it); st[l]={r,x};cnt[tx]+=(r-l+1);cnt.update(tx); void alter(int x,int w){ uf.merge(x,w); cnt[w]+=cnt[x];cnt[x]=0; cnt.update(x);cnt.update(w); void exchange(int x,int y){ uf.exchange(x,y); swap(cnt[x],cnt[y]); cnt.update(x);cnt.update(y); int main() { ios::sync_with_stdio(false); int q,op,l,r,x,w,y; cin>>n>>m>>q; cnt.init(m);cnt[0]=n; st[1]={n,0};uf.init(m); while(q--){ cin>>op; if(op==1) { cin>>l>>r>>x; modify(l,r,x); }else if(op==2){ cin>>x>>w; alter(x,w); }else if(op==3){ cin>>x>>y; exchange(x,y); }else if(op==4){ cin>>w; cout<<cnt[w]<<endl; }else{//op==5 cout<<cnt.maxpos()<<endl; return 0;

子任务1： 暴力枚举分段点，然后对每一段逐个判断。期望得分：10分，代码略。时间复杂度： int n,L,x; cin>>n>>L; for(int i=1;i<=n;++i) {cin>>x;s[i]=s[i-1]+x;} for(int i=1;i<=n;++i) {cin>>m[i];f[i]=LONG_LONG_MAX;} f[0]=0; for(int i=1;i<=n;++i) for(int j=0;j<i;++j)//枚举最后一段的开头，上一段的结尾即j-1 if(m[i]>m[j]) f[i]=min(f[i],f[j]+sqr(s[i]-s[j]-L)); //更优时更新 cout<<f[n]<<endl; return 0;

子任务3： 由于保证 ki​的点。

注意到每次有新点加入凸壳时，其横坐标是递增的，而每次查询时所用的斜率也是递增的。这种双递增的特性使得我们可以使用单调队列来实现这个凸壳的维护。