Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
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: