社区讨论
过不了样例,有无好心人帮我debug一下,谢谢啦
P6492[COCI 2010/2011 #6] STEP参与者 1已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @m3g20t4i
- 此快照首次捕获于
- 2024/11/13 23:46 去年
- 此快照最后确认于
- 2025/11/04 14:46 4 个月前
CPP
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int n,q;
struct Node
{
int l,r,vb,ve,len;
int tmax,lmax,rmax;
}tr[N*4];
void pushup(int u)
{
tr[u].vb = tr[u<<1].vb;tr[u].ve = tr[u<<1|1].ve;
tr[u].lmax = tr[u<<1].lmax;tr[u].rmax = tr[u<<1|1].rmax;
tr[u].tmax = max(tr[u<<1].tmax,tr[u<<1|1].tmax);
if(tr[u<<1].ve!=tr[u<<1|1].vb)
{
tr[u].tmax = max(tr[u].tmax,tr[u<<1].rmax+tr[u<<1].lmax);
if(tr[u<<1].tmax == tr[u<<1].len) tr[u].lmax = tr[u<<1].len+tr[u<<1|1].lmax;
if(tr[u<<1|1].tmax == tr[u<<1|1].len) tr[u].rmax = tr[u<<1|1].len+tr[u<<1].rmax;
}
}
void build(int u,int l,int r)
{
if(l == r) tr[u] = {l,r,1,1,1,1,1,1};
else
{
tr[u] = {l,r,1,1,r-l+1};
int mid = l+r>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify(int u,int x)
{
if(tr[u].l == x && tr[u].r == x)
{
tr[u].vb=1-tr[u].vb;
tr[u].ve=1-tr[u].ve;
}
else
{
int mid = tr[u].l+tr[u].r>>1;
if(x<=mid) modify(u<<1,x);
else modify(u<<1|1,x);
pushup(u);
}
}
int main()
{
cin >> n >> q;
build(1,1,n);
while(q--)
{
int x;
cin >> x;
modify(1,x);
cout << tr[1].tmax << endl;
}
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...