結果

問題 No.925 紲星 Extra
コンテスト
ユーザー maroon_kuri
提出日時 2019-11-09 10:25:28
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 7,610 ms / 10,000 ms
コード長 8,919 bytes
コンパイル時間 2,346 ms
コンパイル使用メモリ 196,320 KB
実行使用メモリ 307,012 KB
最終ジャッジ日時 2024-09-15 04:17:44
合計ジャッジ時間 71,178 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))

using uint=unsigned;
using ull=unsigned long long;

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"{";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<"}";
}

void print(ll x,int suc=1){
	cout<<x;
	if(suc==1)
		cout<<"\n";
	if(suc==2)
		cout<<" ";
}

ll read(){
	ll i;
	cin>>i;
	return i;
}

vi readvi(int n,int off=0){
	vi v(n);
	rep(i,n)v[i]=read()+off;
	return v;
}

template<class T>
void print(const vector<T>&v,int suc=1){
	rep(i,v.size())
		print(v[i],i==int(v.size())-1?suc:2);
}

string readString(){
	string s;
	cin>>s;
	return s;
}

template<class T>
T sq(const T& t){
	return t*t;
}

//#define CAPITAL
void yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<endl;
	#else
	cout<<"Yes"<<endl;
	#endif
	if(ex)exit(0);
}
void no(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<endl;
	#else
	cout<<"No"<<endl;
	#endif
	if(ex)exit(0);
}

constexpr ll ten(int n){
	return n==0?1:ten(n-1)*10;
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

int topbit(signed t){
	return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
	return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
	return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
	return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
	return __builtin_popcount(t);
}
int popcount(ll t){
	return __builtin_popcountll(t);
}
bool ispow2(int i){
	return i&&(i&-i)==i;
}
int mask(int i){
	return (int(1)<<i)-1;
}

bool inc(int a,int b,int c){
	return a<=b&&b<=c;
}

template<class t> void mkuni(vc<t>&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

ll rand_int(ll l, ll r) { //[l, r]
	#ifdef LOCAL
	static mt19937_64 gen;
	#else
    static random_device rd;
    static mt19937_64 gen(rd());
    #endif
    return uniform_int_distribution<ll>(l, r)(gen);
}

//#define SPLAYLAZY

//push は副作用なし
//clean で lazy タグを消去
//find はその部分木内に目標とするノードがあるかどうかを返す
//split は find で見つけたものが右の部分木の left になるように分離する
//ARC033 C
//AOJ DSL2G
template<class N,int S>
struct splaytree{
	struct N2{
		N rw,mg;
		using P=N2*;
		P l,r,p;
		N2():l(0),r(0),p(0){}
		void push(){
			#ifdef SPLAYLAZY
			mg.push(rw);
			if(l)mg.push(l->mg);
			if(r)mg.push(r->mg);
			mg.clean();
			#endif
		}
		P upd(){
			mg=rw.parent();
			if(l)mg=N::merge(l->mg,mg);
			if(r)mg=N::merge(mg,r->mg);
			return this;
		}
		int pos(){
			if(p&&p->l==this)return -1;
			if(p&&p->r==this)return 1;
			return 0;
		}
		void prepare(){
			#ifdef SPLAYLAZY
			if(p)p->prepare();
			push();
			#endif
		}
		void rotate(){
			P q=p,c;
			if(pos()==1){
				c=l;
				l=p;
				p->r=c;
			}else{
				c=r;
				r=p;
				p->l=c;
			}
			if(c)c->p=p;
			p=p->p;
			q->p=this;
			if(p&&p->l==q)p->l=this;
			if(p&&p->r==q)p->r=this;
			q->upd();
		}
		P splay(){
			prepare();
			while(p){
				int a=pos();
				if(p->p){
					if(a==p->pos())p->rotate();
					else rotate();
				}
				rotate();
			}
			return upd();
		}
		/*
		P right(){
			if(r)return r->right();
			else return splay();
		}*/
		P left(){
			if(l)return l->left();
			else return splay();
		}
		template<class F,class...Args>
		P find(F f,Args&&...args){
			if(!(mg.*f)(args...))return 0;
			push();
			P a=0;
			if(l)a=l->find(f,forward<Args>(args)...);
			if(a)return a;
			if((rw.*f)(args...))return splay();
			return r->find(f,forward<Args>(args)...);
		}
		P cutl(){
			if(l){
				l->p=0;
				l=0;
			}
			return upd();
		}
		/*
		P cutr(){
			if(r){
				r->p=0;
				r=0;
			}
			return upd();
		}*/
		P linkl(P x){
			assert(!l);
			l=x;
			if(x)x->p=this;
			return upd();
		}
		/*
		P linkr(){
			assert(!r);
			r=x;
			if(x)x->p=this;
			return upd();
		}*/
	} buf[S];
	using P=N2*;
	vc<P> ps;
	splaytree(){
		rep(i,S)
			ps.pb(buf+i);
	}
	int head=0;
	template<class...Args>
	P nn(Args&&...args){
		P a=ps.back();
		ps.pop_back();
		a->l=0;
		a->r=0;
		a->p=0;
		a->rw=N(forward<Args>(args)...);
		a->mg=a->rw.parent();
		return a;
	}
	P erase(P x){
		x->splay();
		if(x->l)x->l->p=0;
		if(x->r)x->r->p=0;
		P res=merge(x->l,x->r);
		ps.pb(x);
		return res;
	}
	template<class F,class...Args>
	P insert(P r,F f,Args&&...args){
		P x=nn(forward<Args>(args)...);
		P a,b;tie(a,b)=split(r,f,x->mg);
		return merge(merge(a,x),b);
	}
	template<class t>
	P build(vc<t> v){
		vc<P> cur;
		for(auto z:v)cur.pb(nn(z));
		while(cur.size()>1){
			int s=cur.size();
			vc<P> nx((s+1)/2);
			for(int i=0;i<s;i+=2){
				if(i+1<s)nx[i/2]=merge(cur[i],cur[i+1]);
				else nx[i/2]=cur[i];
			}
			swap(nx,cur);
		}
		return cur[0];
	}
	P merge(P a,P b){
		if(!a)return b;
		if(!b)return a;
		return b->splay()->left()->linkl(a->splay());
	}
	template<class F,class...Args>
	pair<P,P> split(P a,F f,Args&&...args){
		if(!a)return {0,0};
		P b=a->find(f,forward<Args>(args)...);
		if(b){
			P c=b->l;
			return {c,b->cutl()};
		}
		return {a,0};
	}
};

struct N{
	int idx,cnt,sum;
	N(int i=0,int c=1,int s=0):idx(i),cnt(c),sum(s){}
	N parent(){
		return *this;
	}
	static N merge(N a,N b){
		return N(b.idx,a.cnt+b.cnt,a.sum+b.sum);
	}
	void push(N&){
	}
	void clean(){
	}
	bool findI(int x){
		return x<=idx;
	}
	bool findN(const N&x){
		return x.idx<=idx;
	}
};

const int S=(1<<16)*41;
using tree=splaytree<N,S>;
using P=tree::P;
tree t;

map<int,tree::P> buf;

struct BIT{
	vi buf;
	int s;
	BIT(int n=0){init(n);}
	void init(int n){buf.assign(s=n,0);}
	void add(int i,int v){
		for(;i<s;i+=(i+1)&(-i-1))
			buf[i]+=v;
	}
	int get(int i){
		int res=0;
		for(;i>=0;i-=(i+1)&(-i-1))
			res+=buf[i];
		return res;
	}
	int sum(int b,int e){
		return get(e-1)-get(b-1);
	}
	int kth(int k){
		int res=0;
		for(int i=topbit(s);i>=0;i--){
			int w=res+(1<<i);
			if(w<=s&&buf[w-1]<=k){
				k-=buf[w-1];
				res=w;
			}
		}
		return res;
	}
};

BIT bit;

vi rawa;

const int L=41;
void add(int i,int v){
	int rv=v;
	rawa[i]=v;
	bit.add(i,v);
	for(;v<(1LL<<L);v+=(v+1)&(-v-1)){
		/*P x=t.nn(i,1,rv);
		P a,b;
		tie(a,b)=t.split(buf[v],&N::find,i);
		buf[v]=t.merge(t.merge(a,x),b);*/
		buf[v]=t.insert(buf[v],&N::findN,i,1,rv);
	}
}

void del(int i,int v){
	bit.add(i,-v);
	for(;v<(1LL<<L);v+=(v+1)&(-v-1)){
		P x=buf[v]->find(&N::findI,i);
		buf[v]=t.erase(x);
	}
}

tuple<int,int,int> ask(int l,int r){
	int m=(r-l+1)/2;
	dmp(m);
	int w=0;
	int cnt=0,sum=0;
	per(i,L){
		int nx=w+(1LL<<i);
		if(nx<=(1LL<<L)){
			if(buf.count(nx-1)){
				P a,b,c;
				tie(a,b)=t.split(buf[nx-1],&N::findI,l);
				tie(b,c)=t.split(b,&N::findI,r);
				int bc=0,bs=0;
				if(b){
					bc=b->mg.cnt;
					bs=b->mg.sum;
				}
				dmp(nx);
				dmp(bc);
				dmp(m);
				if(bc<m){
					m-=bc;
					cnt+=bc;
					sum+=bs;
					w=nx;
				}
				buf[nx-1]=t.merge(t.merge(a,b),c);
			}else{
				w=nx;
			}
		}
	}
	return make_tuple(cnt,sum,w);
}


signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	int n,q;cin>>n>>q;
	vi a=readvi(n);
	
	rawa.resize(n);
	bit.init(n);
	
	rep(i,n)
		add(i,a[i]);
	
	int s=0;
	
	rep(_,q){
		int tp;cin>>tp;
		if(tp==1){
			int x,y;cin>>x>>y;
			x^=s&mask(16);
			y^=s&mask(40);
			
			dmp(x);
			dmp(y);
			
			x--;
			
			del(x,a[x]);
			a[x]=y;
			add(x,a[x]);
		}else{
			int l,r;cin>>l>>r;
			l^=s&mask(16);
			r^=s&mask(16);
			if(l>r)swap(l,r);
			
			dmp(l);
			dmp(r);
			
			l--;
			
			int cnt,sum,m;
			tie(cnt,sum,m)=ask(l,r);
			dmp(cnt);
			dmp(sum);
			dmp(m);
			
			/*{
				vi tmp(rawa.bg+l,rawa.bg+r);
				sort(all(tmp));
				dmp(tmp);
			}*/
			
			int ans=bit.sum(l,r);
			ans-=sum*2;
			ans+=(cnt*2-(r-l))*m;
			
			//cout<<ans<<endl;
			print(ans);
			s^=ans;
		}
	}
}
0