4334096_ac_375ms_4128k.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>

typedef struct node
{
	int L, R;
	int c;
	int l, r;
}Node;

Node root[300000];
int cnt;

void creat_seg_tree(int no, int l, int r)
{
	int mid;

	mid = (l + r) >> 1;
	root[no].L = l;
	root[no].R = r;
	root[no].c = 1;
	if(l == r)
	{
		root[no].l = -1;
		root[no].r = -1;
		return ;
	}
	root[no].l = ++cnt;
	creat_seg_tree(cnt, l, mid);
	root[no].r = ++cnt;
	creat_seg_tree(cnt, mid + 1, r);
}

int c;

void update(int r, int a, int b)
{
	int mid;
	
	if (c == root[r].c)
	{
		return ;
	}

	if (root[r].L == a && root[r].R == b)
	{
		root[r].c = c;
		return ;
	}


	mid = (root[r].L + root[r].R) >> 1;
	

	if (root[r].c)
	{
		root[root[r].l].c = root[r].c;
		root[root[r].r].c = root[r].c;
	}
	
	root[r].c = 0;

	if (b <= mid)
		update(root[r].l, a, b);
	else
	{
		if (a > mid)
			update(root[r].r, a, b);
		else
		{
			update(root[r].l, a, mid);
			update(root[r].r, mid + 1, b);
		}
	}
}

int find(int r, int a, int b)
{
	int mid;
	
	if (root[r].c)
	{
		return root[r].c;
	}

	mid = (root[r].L + root[r].R) >> 1;
	
	if (b <= mid)
		return find(root[r].l, a, b);
	else
	{
		if (a > mid)
			find(root[r].r, a, b);
		else
		{
			return ( find(root[r].l, a, mid) |
				find(root[r].r, mid + 1, b));
		}
	}
}

int num(int n)
{
	int ret = 0;

	while (n)
	{
		n &= (n - 1);
		ret++;
	}
	return ret;
}

int main()
{
	int i, l, t, o;
	char com[2];
	int a, b;

	scanf("%d%d%d", &l, &t, &o);
	cnt = 0;
	creat_seg_tree(0, 0, l - 1);
	for (i = 0; i < o; i++)
	{
		scanf("%s", com);
		if (com[0] == 'C')
		{
			scanf("%d%d%d", &a, &b, &c);
			c--;
			c = (1 << c);
			a--;b--;
			if (a < b)
				update(0, a, b);
			else
				update(0, b, a);
		}
		else
		{
			scanf("%d%d", &a, &b);
			a--;b--;
			if (a < b)
				printf("%d\n", num(find(0, a, b)));
			else
				printf("%d\n", num(find(0, b, a)));
		}
	}
	return 0;
}