수쿼28 1066B

seqquery28.cpp

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

int N, Q, t, l, r; long x;
struct node {
	long a, b, m, n;
	void input() { cin>>a; m=n=a; }
	node operator+(node& R) {
		return {a+R.a, 0, max(m, R.m), min(n, R.n)};
	}
	void down(node& R, int d) {
		if(R.m==R.n) a=R.m<<d, m=R.m, n=R.n;
		else b+=R.b, a+=R.b<<d, m+=R.b, n+=R.b;
	}
	bool apply(int d) {
		if(t==3) { x+=a; return true; }
		if(t==1) { a+=x<<d, b+=x, m+=x, n+=x; return true; }
		if(m-n>1) return false;
		long s=sqrt(m);
		n=sqrt(n);
		if(s==n) a=s<<d;
		else a+=s-m<<d, b+=s-m;
		m=s;
		return true;
	}
} A[1<<18];

void qry(int d=17, int s=0, int i=1) {
	if(l<=s && s+(1<<d)<=r && A[i].apply(d)) return;
	int m=s|1<<--d;
	A[i*2].down(A[i], d);
	A[i*2+1].down(A[i], d);
	if(l<m) qry(d, s, i*2);
	if(r>m) qry(d, m, i*2+1);
	A[i]=A[i*2]+A[i*2+1];
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>N;
	for(int i=0; i<N; i++) A[1<<17|i].input();
	for(int i=1<<17; --i;) A[i]=A[i*2]+A[i*2+1];
	cin>>Q;
	while(Q--) {
		cin>>t>>l>>r; --l, x=0;
		if(t==1) cin>>x;
		qry();
		if(t==3) cout<<x<<'\n';
	}
}

짧다