社区讨论
萌新求助,线段树莫名全输出0
P1558色板游戏参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mi7yznc2
- 此快照首次捕获于
- 2025/11/21 05:55 4 个月前
- 此快照最后确认于
- 2025/11/21 05:55 4 个月前
RT,思路:建30棵线段树。。。
CPP#include <bits/stdc++.h>
using namespace std;
int n,m,k;
struct Node
{
int l,r,la;
int mx;
}t[35][100005];
void BuildT(int it,int id,int l,int r)
{
t[it][id].l=l;
t[it][id].r=r;
t[it][id].la=0;
t[it][id].mx=0;
if(l==r)
{
return;
}
int Mid=(l+r)/2;
BuildT(it,id*2,l,Mid);
BuildT(it,id*2+1,Mid+1,r);
}
void Push(int it,int id)
{
if(t[it][id].la)
{
t[it][id*2].la+=t[it][id].la;
t[it][id*2+1].la+=t[it][id].la;
t[it][id].mx+=t[it][id].la*(t[it][id].r-t[it][id].l+1);
t[it][id].mx=max(t[it][id].mx,0);
t[it][id].la=0;
}
}
void Max(int it,int id,int l,int r,int c)
{
cout << it << " " << id << " " << t[it][id].l << " " << t[it][id].r << " " << l << " " << r <<endl;
if(t[it][id].l==l&&t[it][id].r==r)
{
t[it][id].la+=c;
Push(it,id);
return;
}
Push(it,id);
if(t[it][id*2].r>=r)
{
Max(it,id*2,l,r,c);
}
else if(t[it][id*2+1].l<=l)
{
Max(it,id*2+1,l,r,c);
}
else
{
Max(it,id*2,l,t[it][id*2].r,c);
Max(it,id*2+1,t[it][id*2+1].l,r,c);
}
}
int Query(int it,int id,int l,int r)
{
Push(it,id);
if(t[it][id].l==l&&t[it][id].r==r)
{
return t[it][id].mx;
}
if(t[it][id*2].r>=r)
{
return Query(it,id*2,l,r);
}
else if(t[it][id*2+1].l<=l)
{
return Query(it,id*2+1,l,r);
}
else
{
return Query(it,id*2,l,t[it][id*2].r)+Query(it,id*2+1,t[it][id*2+1].l,r);
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;++i)
{
BuildT(i,1,1,n);
}
// for(int i=1;i<=m;++i)
// {
// for(int j=1;j<=4*n;++j)
// {
// printf("%d %d %d\n",t[i][j].l,t[i][j].r,t[i][j].mx);
// }
// printf("\n\n");
// }
Max(1,1,n,n,1);
while(k--)
{
char c;
int x,y,z;
cin >> c;
scanf("%d%d",&x,&y);
if(c=='C')
{
scanf("%d",&z);
Max(z,1,x,y,1);
for(int i=1;i<=m;++i)
{
if(i==z)
{
continue;
}
Max(i,1,x,y,-1);
}
}
else
{
int ans=0;
for(int i=1;i<=n;++i)
{
if(Query(i,1,x,y)!=0)
{
ans++;
}
}
printf("%d\n",ans);
}
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...