2016ユーティリティC Training for Data Structures B-卿先輩と基本法CDOJ 1325線分樹+離散化

B題:卿先輩と基本法
一節の区間をあげます.長さは1 e 8、Q回操作(Q<=1 e 5)、
操作には二つの種類があります.一つはある区間を染色すること、もう一つはある区間が染色されていない長さを調べることです.
 
離散化+線分樹は区間の染色を求めます.
えっと、離散化は簡単です.私のやり方はsort+unique+lowerです.boundは解決して、チャットの中で柱のおじいさんは突然1つ言って、実はuniqueはないことができて、思って、本当にえっと、番号を求めないで連続しなければならないならば、uniqueがないことができるので、しかし習慣があって、だから大丈夫です.
 
それから、線分樹は区間染色を求めます.これは01染色に相当するので、比較的簡単です.区間更新の時に、直接にこの区間のsumを修正して、lazyの賦値を1にします.下の分区間も全部染色されていますので、下のサブ区間のデータは全部使えなくなります.そして調べた時にlazyを下ろせばいいです.
 
もちろん、この問題は離散化による問題です.離散化後、一つの点は区間を表しています.そして、私の線分樹は閉区間になっていますので、統計に相当するのは点です.例えば、「1、4」の二つのサブ区間は「1、2」と「3、4」です.例えば、1,100,200,300,1,2,3,4に離散化すると、私の線分樹の中の[101,199]はこの区間でなくなってしまいますが、この区間の紛失は明らかに誤りをもたらす可能性があります.そして、私のやり方は各ノードの二つのサブ区間の中のこの部分の情報を表しています.そのサブゾーンの間では得られないので、対応する操作の中で対応する修正をすればいいです.
 
後に考えてみましたが、線分樹が左閉右開区間にあるなら、各点の前後に点を加えてから離散化すると、上のような問題が起こらないようです.感覚的には正しいようですが、深く考えていません.
コード:

#include 
#include 
#include 
#include 
using namespace std;
#define maxq 100005
#define lid (id<<1)
#define rid (id<<1|1)
int N, Q, num;
int data[maxq * 2];
int oper[maxq][3];
struct segtree
{
	int l, r;
	int sum, lazy;
	bool tag;
}tr[maxq * 8];
void discrete()
{
	sort(data + 1, data + 2 * Q + 1);
	num = unique(data + 1, data + 2 * Q + 1) - data;
	/*int t = num;
	for (int i = 2; i < t; ++i)
	{
		if (data[i] - data[i - 1] == 2)
			data[num++] = data[i] - 1;
		else if (data[i] - data[i - 1] >= 2)
		{
			data[num++] = data[i - 1] + 1;
			data[num++] = data[i] - 1;
		}
	}
	sort(data + 1, data + num);*/
	for (int i = 1; i <= Q; ++i)
	{
		oper[i][0] = lower_bound(data, data + num, oper[i][0]) - data;
		oper[i][1] = lower_bound(data, data + num, oper[i][1]) - data;
	}
}
void bulid(int id, int l, int r)
{
	tr[id].l = l; tr[id].r = r;
	if (l == r)
		return;
	int mid = (l + r) >> 1;
	bulid(lid, l, mid);
	bulid(rid, mid + 1, r);
}
void push_down(int id)
{
	if (tr[id].lazy != 0)
	{
		if (tr[id].l < tr[id].r)
		{
			tr[id].tag = 1;
			tr[lid].sum = (data[tr[lid].r] - data[tr[lid].l] + 1)*tr[id].lazy;
			tr[lid].lazy = tr[id].lazy;
			tr[rid].sum = (data[tr[rid].r] - data[tr[rid].l] + 1)*tr[id].lazy;
			tr[rid].lazy = tr[id].lazy;
		}
		tr[id].lazy = 0;
	}
}
void update(int id, int l, int r, int v)
{
	if (l == tr[id].l&&tr[id].r == r)
	{
		tr[id].sum = (data[tr[id].r] - data[tr[id].l] + 1)*v;
		tr[id].lazy = v;
		return;
	}
	push_down(id);
	int mid = (tr[id].l + tr[id].r) >> 1;
	if (r <= mid) update(lid, l, r, v);
	else if (l > mid) update(rid, l, r, v);
	else
	{
		tr[id].tag = 1;
		update(lid, l, mid, v);
		update(rid, mid + 1, r, v);
	}
	tr[id].sum = tr[lid].sum + tr[rid].sum + tr[id].tag*(data[tr[rid].l] - data[tr[lid].r] - 1);
}
int query(int id, int l, int r)
{
	if (l == tr[id].l&&r == tr[id].r)
	{
		return tr[id].sum;
	}
	push_down(id);
	int mid = (tr[id].l + tr[id].r) >> 1;
	if (r <= mid) return query(lid, l, r);
	else if (l > mid) return query(rid, l, r);
	else
	{
		return query(lid, l, mid) + query(rid, mid + 1, r) + tr[id].tag*(data[tr[rid].l] - data[tr[lid].r] - 1);
	}
}
int main()
{
	scanf("%d%d", &N, &Q);
	int a, b, c;
	for (int i = 1; i <= Q; ++i)
	{
		scanf("%d%d%d", &a, &b, &c);
		oper[i][0] = data[2 * i - 1] = b;
		oper[i][1] = data[2 * i] = c;
		oper[i][2] = a;
	}
	discrete();
	bulid(1, 1, num - 1);
	for (int i = 1; i <= Q; ++i)
	{
		if (oper[i][2] == 1)
			update(1, oper[i][0], oper[i][1], 1);
		else if (oper[i][2] == 2)
		{
			printf("%d
", data[oper[i][1]] - data[oper[i][0]] + 1 - query(1, oper[i][0], oper[i][1]));
		}
	}
	return 0;
}