[POJ] 3468. A Simple Problem with Integers

題目連結:http://poj.org/problem?id=3468

---

裸的線段樹，區間加值、區間查和，不過也可以用BIT做掉，不過我不太會QQ

#include <iostream>
#include <utility>
using namespace std;
typedef long long lld;
typedef pair<lld,lld> PLL;
#define FF first
#define SS second

const int N = 100000 + 5;

class SegTree{
	private:
		PLL nodes[N<<2];
		int size;
		inline int lc(int x){return (x<<1)+1;}
		inline int rc(int x){return (x<<1)+2;}
		inline void push(int l, int r, int id){
			if(r-l>1){
				nodes[lc(id)].FF += nodes[id].FF;
				nodes[rc(id)].FF += nodes[id].FF;
			}
			nodes[id].SS += nodes[id].FF * (r-l);
			nodes[id].FF=0;
		}
		inline void pull(int l, int r,int id){
			int mid=(l+r)>>1;
			lld ll = nodes[lc(id)].SS+nodes[lc(id)].FF*(mid-l);
			lld rr = nodes[rc(id)].SS+nodes[rc(id)].FF*(r-mid);
			nodes[id].SS = ll + rr;
		}
		template<typename T>
		void build(T* arr, int l, int r, int id){
			nodes[id].FF=0;
			if(r-l==1){
				nodes[id].SS = arr[l];
			}else{
				int mid=(l+r)>>1;
				build(arr, l, mid, lc(id));
				build(arr, mid, r, rc(id));
				nodes[id].SS = nodes[lc(id)].SS+nodes[rc(id)].SS;
			}
		}
		lld query(int ql, int qr, int l, int r, int id){
			if(r <= ql or qr <= l) return 0;
			push(l,r,id);
			if(ql <= l and r <= qr) return nodes[id].SS;
			int mid=(l+r)>>1;
			return query(ql, qr, l, mid, lc(id))+query(ql, qr, mid, r, rc(id));
		}
		void modify(int ql, int qr, int l, int r, int v, int id){
			if(r <= ql or qr <= l) return;
			push(l, r, id);
			if(ql <= l and r <= qr){
				nodes[id].FF = v;
				return;
			}
			int mid=(l+r)>>1;
			modify(ql, qr, l, mid, v, lc(id));
			modify(ql, qr, mid, r, v, rc(id));
			pull(l, r, id);
		}
	public:
		template<typename T>
		void build(T* arr, int n){
			size=n;
			build(arr, 0, n, 0);
		}
		lld query(int l,int r){
			return query(l, r, 0, size, 0);
		}
		void modify(int l, int r, int v){
			modify(l, r, 0, size, v, 0);
		}
} seg;

int arr[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, q; cin>>n>>q;
	for(int i=0;i<n;i++) cin>>arr[i];
	seg.build(arr,n);
	while(q--){
		char type;cin>>type;
		if(type=='C'){
			int l, r, v;cin>>l>>r>>v;
			seg.modify(l-1,r,v);
		}else if(type=='Q'){
			int l, r;cin>>l>>r;
			cout<<seg.query(l-1,r)<<'\n';
		}
	}
	return 0;
}