社区讨论

过不了样例,有无好心人帮我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 条回复,欢迎继续交流。

正在加载回复...