题解 P1558 【色板游戏】
VenusM1nT
·
·
题解
注意 $x>y$ 的时候要替换，不然会死的很惨……
```cpp
#include<bits/stdc++.h>
#define MAXN 100005
#define MAXT 35
#define iter set <Node>::iterator
using namespace std;
struct Node
{
int l,r;
mutable int val;
bool operator < (const Node &x) const
{
return l<x.l;
}
};
set <Node> s;
int n,m,T;
bool fg[MAXN];
iter Split(int pos)
{
iter it=s.lower_bound((Node){pos,pos,-1});
if(it!=s.end() && it->l==pos) return it;
it--;
Node x=*it;
s.erase(it);
s.insert((Node){x.l,pos-1,x.val});
return s.insert((Node){pos,x.r,x.val}).first;
}
void Assign(int l,int r,int val)
{
iter R=Split(r+1),L=Split(l);
s.erase(L,R);
s.insert((Node){l,r,val});
}
int Query(int l,int r)
{
iter R=Split(r+1),L=Split(l);
int res=0;
memset(fg,0,sizeof(fg));
for(iter it=L;it!=R;it++) fg[it->val]=1;
for(int i=1;i<=T;i++) if(fg[i]) res++;
return res;
}
int main()
{
scanf("%d %d %d",&n,&T,&m);
s.insert((Node){1,n,1});
for(int i=1;i<=m;i++)
{
int x,y,z;
char opt;
cin>>opt;
scanf("%d %d",&x,&y);
if(x>y) swap(x,y);
if(opt=='C')
{
scanf("%d",&z);
Assign(x,y,z);
}
else printf("%d\n",Query(x,y));
}
return 0;
}
```