记录编号	343540	评测结果	AAAAAAAAAA
题目名称	Color the Axis	最终得分	100
用户昵称	Tabing010102	是否通过	通过
代码语言	C++	运行时间	4.638 s
提交时间	2016-11-09 14:37:16	内存使用	0.25 MiB

#include <cstdio>
using namespace std;
const int maxn = 2000000+100;
const int INF = 0x3f3f3f3f;
FILE *fin, *fout;
int n, m;
inline int max(int a, int b) { return a<b?b:a; }
inline int min(int a, int b) { return a<b?a:b; }
struct SEG {
	int n;
	int sumv[maxn<<2];
	int setv[maxn<<2];
	SEG(int n) {
		this->n = n;
		build(1, 1, n);
	}
	void build(int o, int L, int R) {
		setv[o] = INF;
		if(L == R) {
			sumv[o] = 1;
		} else {
			int lc=o*2, rc=o*2+1;
			int M = L + (R-L)/2;
			build(lc, L, M);
			build(rc, M+1, R);
			sumv[o] = sumv[lc] + sumv[rc];
		}
	}
	void upcurpinfo(int o, int L, int R) {
		int lc=o*2, rc=o*2+1;
		if(setv[o] != INF) sumv[o] = setv[o] * (R-L+1);
		else if(R > L) sumv[o] = sumv[lc]+sumv[rc];
	}
	int oL, oR;
	void set(int o, int L, int R) {
		if(L>=oL && R<=oR) {
			setv[o] = 0;
		} else {
			int lc=o*2, rc=o*2+1;
			int M = L + (R-L)/2;
			if(M >= oL) set(lc, L, M); else upcurpinfo(lc, L, M);
			if(M < oR) set(rc, M+1, R); else upcurpinfo(rc, M+1, R);
		}
		upcurpinfo(o, L, R);
	}
	int _sum;
	void qsum(int o, int L, int R) {
		if(setv[o] != INF) {
			_sum += setv[o] * (min(R,oR)-max(L,oL)+1);
		} else if(L>=oL && R<=oR) {
			_sum += sumv[o];
		} else {
			int lc=o*2, rc=o*2+1;
			int M = L + (R-L)/2;
			if(M >= oL) qsum(lc, L, M);
			if(M < oR) qsum(rc, M+1, R);
		}
	}
	void execute_command() {
		int l, r;
		fscanf(fin, "%d%d", &l, &r);
		oL = l; oR = r;
		set(1, 1, n);
		_sum = 0;
		oL = 1; oR = n;
		qsum(1, 1, n);
		fprintf(fout, "%d\n", _sum);
	}
};
int main() {
	fin = fopen("axis.in", "r");
	fout = fopen("axis.out", "w");
	fscanf(fin, "%d%d", &n, &m);
	SEG *D = new SEG(n);
	for(int i = 1; i <= m; i++) D->execute_command();
	return 0;
}