luogu2221 [HAOI2012]高速公路

和sdoi的相关分析很像qwq，推柿子然后线段树搞搞
#include <iostream>

#include <cstdio>

using namespace std;

typedef long long ll;

int n, m, uu, vv, ww;

ll que[3];

char ss[15];

struct SGT{

	ll sum[400005][3], tag[400005];

	//sum[0]: \sum w_i i, sum[1]: \sum w_i i^2, sum[2]: \sum w_i

	void pushDown(int o, int l, int r, int lson, int rson, int mid){

		tag[lson] += tag[o];

		tag[rson] += tag[o];

		sum[lson][0] += (ll)tag[o]*(mid-l+1)*(l+mid)/2;

		sum[lson][1] += (ll)tag[o]*((ll)mid*(mid+1)*(2*mid+1)/6-(ll)(l-1)*l*(2*l-1)/6);

		sum[lson][2] += (ll)tag[o]*(mid-l+1);

		sum[rson][0] += (ll)tag[o]*(r-mid)*(mid+1+r)/2;

		sum[rson][1] += (ll)tag[o]*((ll)r*(r+1)*(2*r+1)/6-(ll)mid*(mid+1)*(2*mid+1)/6);

		sum[rson][2] += (ll)tag[o]*(r-mid);

		tag[o] = 0;

	}

	void update(int o, int l, int r, int x, int y, int k){

		if(l>=x && r<=y){

			sum[o][0] += (ll)k*(r-l+1)*(l+r)/2;

			sum[o][1] += (ll)k*((ll)r*(r+1)*(2*r+1)/6-(ll)(l-1)*l*(2*l-1)/6);

			sum[o][2] += (ll)k*(r-l+1);

			tag[o] += k;

		}

		else{

			int mid=(l+r)>>1;

			int lson=o<<1;

			int rson=lson|1;

			if(tag[o])	pushDown(o, l, r, lson, rson, mid);

			if(x<=mid)	update(lson, l, mid, x, y, k);

			if(mid<y)	update(rson, mid+1, r, x, y, k);

			for(int i=0; i<3; i++)

				sum[o][i] = sum[lson][i] + sum[rson][i];

		}

	}

	void query(int o, int l, int r, int x, int y){

		if(l>=x && r<=y)

			for(int i=0; i<3; i++)

				que[i] += sum[o][i];

		else{

			int mid=(l+r)>>1;

			int lson=o<<1;

			int rson=lson|1;

			if(tag[o])	pushDown(o, l, r, lson, rson, mid);

			if(x<=mid)	query(lson, l, mid, x, y);

			if(mid<y)	query(rson, mid+1, r, x, y);

		}

	}

}sgt;

ll gcd(ll a, ll b){

	return !b?a:gcd(b, a%b);

}

int main(){

	cin>>n>>m;

	while(m--){

		scanf("%s", ss);

		if(ss[0]=='C'){

			scanf("%d %d %d", &uu, &vv, &ww);

			vv--;

			sgt.update(1, 1, n, uu, vv, ww);

			sgt.query(1, 1, n, 1, 1);

		}

		else{

			scanf("%d %d", &uu, &vv);

			que[0] = que[1] = que[2] = 0;

			ll fm=(ll)(vv-uu+1)*(vv-uu)/2;

			vv--;

			sgt.query(1, 1, n, uu, vv);

			ll ans=(ll)(uu+vv)*que[0]-que[1]+(ll)(vv+1)*(1-uu)*que[2];

			ll f=gcd(ans, fm);

			printf("%lld/%lld\n", ans/f, fm/f);

		}

	}

	return 0;

}
巴特西

luogu2221 [HAOI2012]高速公路

最新文章

热门文章
