实测虽然都wa(可能是代码问题),但没有tle的,是否说明此做法可行?
by Heart_Of_Iron_4 @ 2024-02-07 17:59:38
代码(如果这种做法可以,请帮忙调一下。谢谢!)
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(qw,we,er) for(int qw=we;qw<=er;++qw)
#define mid ((l+r)/2)
set<int> t1;
char t2;
int n,t,o,a[1919810],t3,t4,t5;
bool flag;
//a:-1(the node's color isn't same)
// N+(the node's same color)
void checkdown(int k)
{
if(a[k]!=-1)
{
if(a[k*2]!=0)a[k*2]=a[k];
if(a[k*2+1]!=0)a[k*2+1]=a[k];
}
}
void checkup(int k)
{
flag=1;
if(a[k]%2==0)
{
if(a[k]==a[k+1]&&a[k]!=-1)
flag=a[k/2]==a[k],a[k/2]=a[k];
if(a[k]==a[k+1]&&a[k]==-1)
flag=a[k/2]==-1,a[k/2]=-1;
if(a[k]!=a[k+1]&&a[k+1]!=0)
flag=a[k/2]==-1,a[k/2]=-1;
if(a[k+1]==0)
flag=a[k/2]==a[k],a[k/2]=a[k];
if(!flag)checkup(k/2);
}
if(a[k]%2==1)
{
if(a[k]==a[k-1]&&a[k]!=-1)
flag=a[(k-1)/2]==a[k],a[(k-1)/2]==a[k];
if(a[k]==a[k-1]&&a[k]==-1)
flag=a[(k-1)/2]==-1,a[(k-1)/2]=-1;
if(a[k]!=a[k-1]&&a[k-1]!=0)
flag=a[(k-1)/2]==-1,a[(k-1)/2]=-1;
if(a[k-1]==0)
flag=a[(k-1)/2]==a[k],a[(k-1)/2]=a[k];
if(!flag)checkup((k-1)/2);
}
}
void settree(int l,int r,int k)
{
if(l>r)return;
if(l==r){
a[k]=1;return;
}
a[k]=1;
settree(l,mid,k*2);
settree(mid+1,r,k*2+1);
}
void paint(int l,int r,int k,int c,int cl,int cr)
{
if(cl>cr||cl>r||cr<l)return;
if(l==cl&&r==cr)
{
a[k]=c;
checkup(k);
return;
}
checkdown(k);
paint(l,mid,k*2,c,cl,min(cr,mid));
paint(mid+1,r,k*2+1,c,max(cl,mid+1),cr);
}
void survey(int l,int r,int k,int sl,int sr)
{
if(sl>sr||sr<l||sl>r)return;
if(l>=sl&&r<=sr&&a[k]!=-1)
{
t1.insert(a[k]);
return;
}
checkdown(k);
survey(l,mid,k*2,sl,min(sr,mid));
survey(mid+1,r,k*2+1,max(mid+1,sl),sr);
}
int su(int qw,int we)
{
t1.clear();
survey(1,n,1,qw,we);
return t1.size();
}
signed main()
{
scanf("%lld%lld%lld",&n,&t,&o);
settree(1,n,1);
o=o*2;
while(o--)
{
// cerr<<o<<endl;
scanf("%c",&t2);
if(t2=='C')
{
scanf("%lld%lld%lld",&t3,&t4,&t5);
if(t3>t4)swap(t3,t4);
paint(1,n,1,t5,t3,t4);
}
if(t2=='P')
{
scanf("%lld%lld",&t3,&t4);
if(t3>t4)swap(t3,t4);
printf("%lld\n",su(t3,t4));
}
}
return 0;
}
```
by Heart_Of_Iron_4 @ 2024-02-07 18:00:34
<https://www.luogu.com.cn/record/146473149>
by Heart_Of_Iron_4 @ 2024-02-07 18:01:08