Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎报名第四届北京大学游戏对抗邀请赛!

终于AC(附代码和注释)

Posted by Zechariah at 2018-06-10 23:22:56 on Problem 2777
#include <iostream>
#include <cstdio>
#define N 400000+100
#define jh(x,y) x^=y^=x^=y/*这是两数交换*/
using namespace std;
struct {
	int left;
	int right;
	int delta;
	int pained;//我用的是二进制来存储颜色信息
}tree[N];
int L, O, T;
void pushdown(int p)//p点的delta需要向下传递,把下面的区间都染色
{
	if (tree[p].delta)
	{
		tree[p * 2].delta = tree[p * 2 + 1].delta = tree[p].delta;
		tree[p * 2].pained = tree[p * 2 + 1].pained = (1 << tree[p].delta);
		tree[p].delta = 0;
	}
}
int cou(int x)//计算颜色数
{
	int sum = 0;
	while (x)
	{
		if (x&1)
			++sum;
		x >>= 1;
	}
	return sum;
}
void build(int p, int l, int r)//建树
{
	tree[p].pained = 2;
	tree[p].left = l;
	tree[p].right = r;
	if (l == r)
		return;
	int mid = (l + r) / 2;
	build(p * 2, l, mid);
	build(p * 2 + 1, mid + 1, r);
}
int getsum(int p, int l, int r)//得到l到r区间内的颜色状态
{
	if (tree[p].left == l && tree[p].right == r)return tree[p].pained;//直接返回该区间的颜色状态
	pushdown(p);//向下更新
        //底下就是线段树的基本操作了
	int mid = (tree[p].left + tree[p].right) / 2;
	if (r <= mid)return getsum(2 * p, l, r);
	if (l>mid)return getsum(2 * p + 1, l, r);
	return getsum(2 * p, l, mid) | getsum(2 * p + 1, mid + 1, r);//左右区间的状态要合并
}
void updata(int p, int l, int r, int data)//染色
{
	if (tree[p].left == l && tree[p].right == r)//找到区间的话直接染区间
	{
		tree[p].pained = (1 << data);
		tree[p].delta = data;//记录下当前区间的颜色,为向下更新做准备
		return;
	}
	pushdown(p);//向下更新
	int mid = (tree[p].left + tree[p].right) / 2;
	if (r <= mid)updata(p * 2, l, r, data);
	else if (l>mid)updata(p * 2 + 1, l, r, data);
	else
	{
		updata(p * 2, l, mid, data);
		updata(p * 2 + 1, mid + 1, r, data);
	}
	tree[p].pained = tree[2 * p].pained | tree[2 * p + 1].pained;
}

int main(void)
{
	scanf("%d%d%d", &L, &T, &O);
	build(1, 1, L);
	while (O--)
	{
		char s[2];
		scanf("%s", s);
		if (*s == 'C')
		{
			int x, y, z;
			scanf("%d%d%d", &x, &y, &z);
			if (x>y)jh(x, y);
			updata(1, x, y, z);
		}
		else
		{
			int x, y;
			scanf("%d%d", &x, &y);
			if (x>y)jh(x, y);
			printf("%d\n", cou(getsum(1, x, y)));
		}
	}
	return 0;
}
/*
5 3 5
C 1 3 2
P 2 4
C 3 5 3
P 1 5
P 3 4

2
2
1
*/

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator