首页 > 其他分享 >P6492 [COCI2010-2011#6] STEP

P6492 [COCI2010-2011#6] STEP

时间:2024-02-26 16:16:52浏览次数:26  
标签:node int tree mid len STEP build P6492 2011

原题链接

题解

单点修改线段树,向上更新,再注意下转移方程就行了

code

#include<bits/stdc++.h>
using namespace std;
int tree[800005]={0};
int len[800005][2][2]={0};//代表第几个节点,0/1在左/右边的最大有效长度
int a[200005];
void pushup(int node,int l,int r,int mid)
{
    tree[node]=max(max(tree[node*2],tree[node*2+1]),max(len[node*2][1][1]+len[node*2+1][0][0],len[node*2][0][1]+len[node*2+1][1][0]));
    len[node][0][0]=len[node*2][0][0];
    len[node][1][0]=len[node*2][1][0];
    len[node][0][1]=len[node*2+1][0][1];
    len[node][1][1]=len[node*2+1][1][1];
    if(len[node*2][0][0]==mid-l+1)len[node][0][0]+=len[node*2+1][1-a[mid]][0];
    if(len[node*2][1][0]==mid-l+1)len[node][1][0]+=len[node*2+1][1-a[mid]][0];
    if(len[node*2+1][0][1]==r-mid)len[node][0][1]+=len[node*2][1-a[mid+1]][1];
    if(len[node*2+1][1][1]==r-mid)len[node][1][1]+=len[node*2][1-a[mid+1]][1];
}

void build(int node,int l,int r)
{
    if(l==r)
    {
        a[l]=0;
        tree[node]=1;
        len[node][0][0]=1;
        len[node][0][1]=1;
        //printf("%d:%d\n",node,tree[node]);
        return;
    }

    int mid=(l+r)/2;
    build(node*2,l,mid);
    build(node*2+1,mid+1,r);
    pushup(node,l,r,mid);
   // printf("%d:%d\n",node,tree[node]);
}
void update(int node,int l,int r,int x)
{
    if(l==r&&r==x)
    {
        len[node][a[r]][1]=0;
        len[node][a[r]][0]=0;
        a[r]^=1;
        len[node][a[r]][1]=1;
        len[node][a[l]][0]=1;
        return;
    }

    int mid=(l+r)/2;

    if(x<=mid) update(node*2,l,mid,x);
    else update(node*2+1,mid+1,r,x);
    pushup(node,l,r,mid);
}
int main()
{
    int n,q;
    cin>>n>>q;

    build(1,1,n);
    while(q--)
    {
        int x;
        cin>>x;
        update(1,1,n,x);
        cout<<tree[1]<<endl;
        //for(int i=1;i<=n;i++) cout<<a[i]<<" ";
       // cout<<endl<<endl;
    }

    //for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    return 0;
}

标签:node,int,tree,mid,len,STEP,build,P6492,2011
From: https://www.cnblogs.com/pure4knowledge/p/18034571

相关文章

  • P4569 [BJWC2011] 禁忌 题解
    题目传送门前置知识AC自动机|矩阵加速递推解法对于一段固定的文本串,由于重叠的模式串不对伤害产生贡献,故考虑贪心,每碰到出现一个模式串将其分为一段,最终这个文本串的伤害就是划分次数。类似luoguP3193[HNOI2008]GT考试,令\(f_{i,j}\)表示前\(i\)个字符,当前运行到......
  • #根号分治,分块#洛谷 5309 [Ynoi2011] 初始化
    题目传送门分析如果\(x\)比较大那么可以暴力修改,\(x\)比较小的话可以用数组打标记查询的时候对于暴力修改的部分可以分块,暴力修改的同时需要给块打标记如果\(x\)比较小的情况,一段区间相当于是中间很多段周期加上前后缀(当然可以直接区间减但是我被卡常了)我调的块长是160......
  • 适用于 Amazon Step Functions 的低代码可视化新工作流 Workflow Studio, 现已在 Amaz
    今天,我们非常欣喜地宣布现已在AmazonApplicationCompose中推出AmazonStepFunctionsWorkflowStud。通过这款全新的集成应用,工作流与应用程序资源开发便可整合到统一的可视化基础设施即代码(IaC)生成器。对于使用AmazonStepFunctionsWorkflowStudio创建工作流与......
  • A trip through the Graphics Pipeline 2011: Index
    原文地址https://fgiesen.wordpress.com/2011/07/09/a-trip-through-the-graphics-pipeline-2011-index/Welcome.ThisistheindexpageforaseriesofblogpostsI’mcurrentlywritingabouttheD3D/OpenGLgraphicspipelinesasactuallyimplementedbyGPUs.Alot......
  • P3654 First Step (ファーストステップ)
    FirstStep(ファーストステップ)题目背景知らないことばかりなにもかもが(どうしたらいいの?)一切的一切尽是充满了未知数(该如何是好)それでも期待で足が軽いよ(ジャンプだ!)但我仍因满怀期待而步伐轻盈(起跳吧!)温度差なんていつか消しちゃえってね冷若冰霜的态度有朝一日将会消......
  • P3157 [CQOI2011] 动态逆序对 题解
    题目链接:动态逆序对常见经典题,理解一个数对逆序对贡献计算即可。对于一个数而言,它在一个序列中的逆序对有两部分贡献,一部分为前面比它严格大的数,另一部分为后面比它严格小的数,有道二莫题也是基于此去考虑的。考虑最开始知道了总逆序数,每次删除一个数逆序数会减少两部分值,显然就......
  • P1873 [COCI 2011/2012 #5] EKO / 砍树
    题目链接:一、本题为什么能想到利用二分解决?\(1.\)有单调性提高伐木机的高度,显然地,得到的木头会减少。同样地,放低得到的木头会增多。而正因为答案有单调性,所以我们可以使用二分。\(2.\)数据范围大如果采用暴力枚举,时间复杂度为\(O(n\cdotm)\)会超时。用二分优化后时间......
  • [NOIP2011 提高组] 聪明的质监员
    原题链接首先要读懂题目啊:[Wj>=W]其实是一种bool表达,即大于等于时取1,小于时取0,然后再进行求和。根据要求出最小值大概可以猜测要运用二分,那么我们来判断单调性,首先W在所有矿石的最大最小值之间取值,W越小Y越大,W越大Y越小(观察和推理都很容易得到),那么Y是符合单调性的,即可以运用......
  • [NOI2011] 阿狸的打字机
    把询问全部放到树上,离线dfs处理点击查看代码#include<bits/stdc++.h>usingnamespacestd;strings;intt[100005][26],tot,cnt,r[100005],fa[100005],fail[100005],dfn[100005],w[100005],sum,ans[100005];boolb[100005];vector<int>a[100005];vector<int>o[1000......
  • 排队(利用step by step解题)(动态规划+概率)
    第2题   排队(利用stepbystep解题)查看测评数据信息您刚刚在超市购物,然后前往结账。有两条队伍可用。第一个队伍目前有len1人,而第二个队伍有len2人。你想知道排在第一个队伍比排在第二条队伍“好”(即更早轮到你)的概率。第一个队伍的收银员准备开始给第一个队伍的第一个人......