[TIOJ] 1227. 一個數列

題目連結:http://tioj.infor.org/problems/1227

---

序列小技巧，若允許離線或像本題保證修改完才會有查詢，可以用類似懶標記的方式，把序列的修改存下來(修改$[L,R)$則在L加R減，反之亦然)，然後查詢時就把序列累推回去，並加回原序列，不過這題有點煩的地方是奇偶項要分成兩條處理

#include "lib1227.h"

long long odd[1000003]={0},even[1000003]={0};
long long* D; 
int N;
bool isSUM=false;

void init(int n, long long d[]){
	N=n;
	D=d;
}

void change(int a, int b, long long k){
	if(a%2==0){
		//a是偶數
		even[a/2]-= k;
		odd[a/2] += k;
		if((b-a)%2==0){
			//共有奇數個
			//因a是偶數，故b為偶
			even[b/2+1]+=k;
			odd[b/2] -=k;
		}else{
			//共有偶數個
			//因a是偶數，故b為奇
			even[b/2+1]+=k;
			odd[b/2+1] -=k;
		}
	}else{
		//a是奇數
		even[a/2+1] += k;
		odd[a/2]-= k;
		if((b-a)%2==0){
			//共有奇數個
			//因a是奇數，故b為奇
			even[b/2+1]-=k;
			odd[b/2+1] +=k;
		}else{
			//共有偶數個
			//因a是奇數，故b為偶
			even[b/2+1]-=k;
			odd[b/2]+=k;
		}
	}
}

long long query(int c){
	if(!isSUM){
		for(int i=1;i<N/2;i++){
			odd[i] += odd[i-1];
			even[i]+=even[i-1];
		}
		if(N%2==1)
			even[N/2]+=even[N/2-1];
		isSUM=true;
	}
	if(c%2==0)
		return D[c]+even[c/2];
	return D[c]+odd[c/2];
}

C++