ARC030 D

再びJOI OBとして活動。こういうのは5時間コンテストでやるべきであって、90分4問コンテストでやるべき問題じゃない。

平方分割で気合。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int SQ=500;
int c[210000];
struct wolf{
	vector<long long>v;
	long long sum;
	long long ad;
	wolf(){
		v.clear();sum=0;ad=0;
	}
};
long long val[210000];
vector<wolf>li;
vector<pair<int,long long> >ez;
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%d",c+i);
	wolf tmp;
	for(int i=0;i<a;i++){
		tmp.v.push_back(c[i]);
		tmp.sum+=c[i];
		if(i%400==399||i==a-1){
			li.push_back(tmp);
			tmp=wolf();
		}
	}
	for(int i=0;i<li.size();i++)ez.push_back(make_pair(i,0));
	for(int i=0;i<b;i++){
		int t;scanf("%d",&t);
		if(t==1){
			int p,q,r;scanf("%d%d%d",&p,&q,&r);
			p--;
			int at=0;
			vector<pair<int,long long> > toe;
			for(int j0=0;j0<ez.size();j0++){
				int j=ez[j0].first;
				if(p<=at&&at+li[j].v.size()<=q){
					toe.push_back(make_pair(j,ez[j0].second+r));
				//	ez[j0].second+=r;
				}else if(at<q&&p<at+li[j].v.size()){
					tmp=wolf();
					for(int k=0;k<p-at;k++){
						tmp.v.push_back(li[j].v[k]+ez[j0].second);
						tmp.sum+=li[j].v[k]+ez[j0].second;
					}
					if(tmp.v.size()){toe.push_back(make_pair(li.size(),0));li.push_back(tmp);}
					tmp=wolf();
					for(int k=max(0,p-at);k<min(q-at,(int)li[j].v.size());k++){
						tmp.v.push_back(li[j].v[k]+ez[j0].second);
						tmp.sum+=li[j].v[k]+ez[j0].second;
					}
					toe.push_back(make_pair(li.size(),r));
					li.push_back(tmp);
					tmp=wolf();
					for(int k=q-at;k<li[j].v.size();k++){
						tmp.v.push_back(li[j].v[k]+ez[j0].second);
						tmp.sum+=li[j].v[k]+ez[j0].second;
					}
					if(tmp.v.size()){toe.push_back(make_pair(li.size(),0));li.push_back(tmp);}
				}else toe.push_back(ez[j0]);
				at+=li[j].v.size();
			}
			ez=toe;
		}
		if(t==2){
			vector<pair<int,long long> >copy;
			wolf cL;
			wolf cR;
			int p,q,r,s;
			scanf("%d%d%d%d",&p,&q,&r,&s);
			p--;r--;
			int at=0;
			for(int j0=0;j0<ez.size();j0++){
				int j=ez[j0].first;
				if(r<=at&&at+li[j].v.size()<=s){
					copy.push_back(ez[j0]);	
				}else if(at<s&&r<at+li[j].v.size()){
					if(at+li[j].v.size()<s){
						for(int k=max(0,r-at);k<min(s-at,(int)li[j].v.size());k++){
							cL.v.push_back(li[j].v[k]+ez[j0].second);
							cL.sum+=li[j].v[k]+ez[j0].second;
						}	
					}else{
						for(int k=max(0,r-at);k<min(s-at,(int)li[j].v.size());k++){
							cR.v.push_back(li[j].v[k]+ez[j0].second);
							cR.sum+=li[j].v[k]+ez[j0].second;
						}
					}
				}
				at+=li[j].v.size();
			}
			int L=li.size();
			li.push_back(cL);
		//	for(int j=0;j<cL.v.size();j++)printf("%d ",cL.v[j]);printf("\n");
			int R=li.size();
			li.push_back(cR);
			//for(int j=0;j<cR.v.size();j++)printf("%d ",cR.v[j]);printf("\n");
			vector<pair<int,long long> >toe;
			bool in=false;
			at=0;
			for(int j0=0;j0<ez.size();j0++){
				int j=ez[j0].first;
				if(li[j].v.size()==0)continue;
				if(at+li[j].v.size()<=p)toe.push_back(ez[j0]);
				else if(q<=at)toe.push_back(ez[j0]);
				/*else if(p<=at&&at+li[j].v.size()<=q){
					tmp=wolf();
					if(!in){
						in=true;
						toe.push_back(L);
						for(int k=0;k<copy.size();k++)toe.push_back(copy[k]);
						toe.push_back(R);
					}
				*/
				else{
					if(at<p){
						tmp=wolf();
						for(int k=0;k<p-at;k++){
							tmp.v.push_back(li[j].v[k]+ez[j0].second);
							tmp.sum+=li[j].v[k]+ez[j0].second;
						}
						toe.push_back(make_pair(li.size(),0));
						li.push_back(tmp);
					}
					if(!in){
						in=true;
						if(cL.v.size())toe.push_back(make_pair(L,0));
						for(int k=0;k<copy.size();k++)toe.push_back(copy[k]);
						if(cR.v.size())toe.push_back(make_pair(R,0));
					}
					if(at+li[j].v.size()>q){
						tmp=wolf();
						for(int k=q-at;k<li[j].v.size();k++){
							tmp.v.push_back(li[j].v[k]+ez[j0].second);
							tmp.sum+=li[j].v[k]+ez[j0].second;
						}
						toe.push_back(make_pair(li.size(),0));
						li.push_back(tmp);
					}
				}
				at+=li[j].v.size();
			}
			ez=toe;
		}
		if(t==3){
			int p,q;
			scanf("%d%d",&p,&q);p--;
			long long ret=0;
			int at=0;
			for(int j0=0;j0<ez.size();j0++){
				int j=ez[j0].first;
				if(p<=at&&at+li[j].v.size()<=q){
					ret+=li[j].sum+ez[j0].second*li[j].v.size();
				
				}else if(at<q&&p<at+li[j].v.size()){
					for(int k=max(0,p-at);k<min(q-at,(int)li[j].v.size());k++){
						ret+=ez[j0].second+li[j].v[k];
					}
				//		printf("%lld\n",ret);
				}
				at+=li[j].v.size();
			}
			printf("%lld\n",ret);
		}
	/*	for(int j0=0;j0<ez.size();j0++){
			printf("[");
			int j=ez[j0].first;
			for(int k=0;k<li[j].v.size();k++){
				if(k)printf(",");printf("%d",li[j].v[k]+ez[j0].second);
			}printf("](%lld) ",li[j].sum+ez[j0].second*li[j].v.size());
		}printf("\n");*/
		if(i%SQ==SQ-1){
			int at=0;
			for(int j0=0;j0<ez.size();j0++){
				int j=ez[j0].first;
				for(int k=0;k<li[j].v.size();k++){
					val[at++]=li[j].v[k]+ez[j0].second;
				}
			}
			li.clear();
			tmp=wolf();
			for(int j=0;j<a;j++){
				tmp.v.push_back(val[j]);
				tmp.sum+=val[j];
				if(j%400==399||j==a-1){
					li.push_back(tmp);
					tmp=wolf();
				}
			}
			ez.clear();
			for(int j=0;j<li.size();j++)ez.push_back(make_pair(j,0));
		}
	}
}