ODT求助(Q _ Q)
  • 板块P5350 序列
  • 楼主_outcast_
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/11/17 17:55
  • 上次更新2023/11/4 00:19:40
查看原帖
ODT求助(Q _ Q)
376125
_outcast_楼主2021/11/17 17:55

能过样例,但是全部 RE + MLE 大佬们可以康康我哪里会挂掉吗

QwQwQwQwQwQwQwQwQwQwQ

#include<bits/stdc++.h>
#define IT set<node>::iterator
using namespace std;
inline int read(){
	int x=0;char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
	return x;
}
const int mod=1e9+7;
int n,m;
struct node{
	int l,r;
	mutable int v;
	node(int l,int r=0,int v=0):l(l),r(r),v(v){}
	bool operator <(const node &xx)const{
		return l<xx.l;
	}
};
set<node> s;
IT split(int pos){
	IT it=s.lower_bound(node(pos));
	if(it!=s.end()&&(it->l)==pos) return it;
	it--;
	if((it->r)<pos) return s.end();
	int l=(it->l),r=(it->r),v=(it->v);
	s.erase(it);
	s.insert(node(l,pos-1,v));
	return s.insert(node(pos,r,v)).first;
}
void Assign(int l,int r,int x){
	IT itr=split(r+1),itl=split(l);
	s.erase(itl,itr);
	s.insert(node(l,r,x));
}
void Add(int l,int r,int x){
	IT itr=split(r+1),itl=split(l);
	for(IT i=itl;i!=itr;i++) (i->v)=(0ll+(i->v)+x)%mod;
}
void Copy(int l1,int r1,int l2,int r2){
	IT itr1=split(r1+1),itl1=split(l1);
	IT itr2=split(r2+1),itl2=split(l2);
	int tmp=l2-l1;
	s.erase(itl2,itr2);
	for(IT i=itl1;i!=itr1;i++){
		int l=(i->l),r=(i->r),v=(i->v);
		s.insert(node(l+tmp,r+tmp,v));
	}
}
void Swap(int l1,int r1,int l2,int r2){
	IT itr1=split(r1+1),itl1=split(l1);
	IT itr2=split(r2+1),itl2=split(l2);
	vector<node> v1,v2;
	int tmp=l2-l1;
	for(IT i=itl1;i!=itr1;i++) v1.push_back(*i);
	for(IT i=itl2;i!=itr2;i++) v2.push_back(*i);
	s.erase(itl1,itr1);
	s.erase(itl2,itr2);
	for(int i=0;i<v1.size();i++){
		node it=v1[i];
		int l=it.l,r=it.r,v=it.v;
		s.insert(node(l+tmp,r+tmp,v));
	}
	for(int i=0;i<v2.size();i++){
		node it=v2[i];
		int l=it.l,r=it.r,v=it.v;
		s.insert(node(l-tmp,r-tmp,v));
	}
}
void Reverse(int l,int r){
	IT itr=split(r+1),itl=split(l);
	stack<node> st;
	for(IT i=itl;i!=itr;i++) st.push(*i);
	s.erase(itl,itr);
	int now=l;
	while(st.size()){
		node it=st.top(); st.pop();
		int l=it.l,r=it.r,v=it.v;
		int len=r-l+1;
		s.insert(node(now,now+len-1,v));
		now+=len;
	}
}
int query(int l,int r){
	IT itr=split(r+1),itl=split(l);
	int ret=0;
	for(IT i=itl;i!=itr;i++){
		int l=(i->l),r=(i->r),v=(i->v);
		int sum=(1ll*v*(r-l+1))%mod;
		ret=(0ll+ret+sum)%mod;
	}
	return ret;
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		int x=read();
		s.insert(node(i,i,x));
	}
	while(m--){
		int op=read();
		if(op==1){
			int l=read(),r=read();
			printf("%d\n",query(l,r));
		}
		if(op==2){
			int l=read(),r=read(),x=read();
			Assign(l,r,x);
		}
		if(op==3){
			int l=read(),r=read(),x=read();
			Add(l,r,x);
		}
		if(op==4){
			int l1=read(),r1=read(),l2=read(),r2=read();
			Copy(l1,r1,l2,r2);
		}
		if(op==5){
			int l1=read(),r1=read(),l2=read(),r2=read();
			Swap(l1,r1,l2,r2);
		}
		if(op==6){
			int l=read(),r=read();
			Reverse(l,r);
		}
	}
	for(IT it=s.begin();it!=s.end();it++)
	    for(int i=(it->l);i<=(it->r);i++) printf("%d ",(it->v));
}
2021/11/17 17:55
加载中...