首页 > 其他分享 >题解:P3968 [TJOI2014] 电源插排

题解:P3968 [TJOI2014] 电源插排

时间:2024-09-09 21:02:20浏览次数:9  
标签:node emplace 插排 int 题解 void TJOI2014 itv return

题意

维护一个 \(01\) 串,初始均为 \(0\),支持:

  • 单点将 \(1\) 修改为 \(0\)。
  • 查询区间中 \(1\) 的个数。
  • 查询最长且最靠右的连续 \(0\) 段的靠右的中点,并将其改为 \(1\)。

分析

第一个操作和第二个操作显然使用动态开点线段树维护。

我们只需要解决第三个操作。

我们用平衡树存储连续的 \(0\) 段的左右端点。

维护两棵平衡树,一棵按区间的左端点从小到大排序,另一棵以区间长度为第一关键字,左端点为第二关键字从大到小排序。

询问的时候只需要在第二棵平衡树中取出其最大的元素。

考虑修改操作带来的影响。

单点修改为 \(1\) 会导致一段连续的 \(0\) 段断开成为至多 \(2\) 段。

分类讨论处理一下段的分裂情况。

单点修改为 \(0\) 会导致至多两段连续的 \(0\) 段合并为同一段。

在第一棵树上二分找出插入点前后的连续段,同样分类讨论一下段的合并情况。

时间复杂度 \(O(q\log n+q\log q)\)。


发现平衡树只需要支持查前驱后继,所以可以使用 set 实现。

可以向 set 中加入两个哨兵区间 \([-1,-2],[n+2,n+1]\) 以避免越界分类讨论。

Code

#include<bits/stdc++.h>
using namespace std;

struct SegT
{
    struct node
    {
        uint32_t sum;
        node *lc, *rc;
        node() {lc=rc=0; sum=0;}
    }*rt;

    #define mid ((l+r)>>1)
    #define lson x->lc, l, mid
    #define rson x->rc, mid+1, r

    void modify(node *&x, int l, int r, int p, int v)
    {
        if(!x) x=new node;
        x->sum+=v;
        if(l==r) return;
        if(p<=mid) modify(lson, p, v);
        if(p>mid)  modify(rson, p, v);
    }

    uint32_t query(node *x, int l, int r, int L, int R)
    {
        if(!x) return 0;
        if(L<=l&&r<=R) return x->sum;
        uint32_t ret=0;
        if(L<=mid) ret+=query(lson, L, R); 
        if(R>mid)  ret+=query(rson, L, R); 
        return ret;
    }
}tr;

struct itv
{
    int l, r;
    int pos() {return (l+r+1)>>1;}
    itv(int L, int R) {l=L, r=R;}
};

#define len(x) (x.r-x.l+1)

struct cmp1{bool operator()(itv a, itv b)const{return a.l<b.l;}};
struct cmp2{bool operator()(itv a, itv b)const{return len(a)==len(b)?a.l>b.l:len(a)>len(b);}};

set<itv, cmp1> s1;
set<itv, cmp2> s2;
map<int, int> pos;

void emplace(int x, int y) {s1.emplace(x, y), s2.emplace(x, y);}
void emplace(itv &x) {s1.emplace(x), s2.emplace(x);}
void erase(itv &x) {s1.erase(x), s2.erase(x);}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, q, l, r, k;
    cin>>n>>q;
    emplace(1, n);
    emplace(-1, -2);
    emplace(n+2, n+1);
    while(q--)
    {
        cin>>k;
        if(!k)
            cin>>l>>r, 
            cout<<tr.query(tr.rt, 1, n, l, r)<<'\n';
        else
        {
            if(!pos[k])
            {
                auto seg=*s2.begin();
                erase(seg);
                int p=seg.pos();
                pos[k]=p;
                tr.modify(tr.rt, 1, n, p, 1);
                if(p!=seg.l) emplace(seg.l, p-1);
                if(p!=seg.r) emplace(p+1, seg.r);
            }
            else
            {
                int p=pos[k];
                pos[k]=0;
                tr.modify(tr.rt, 1, n, p, -1);
                auto it=s1.lower_bound({p, 0});
                auto seg2=*it, seg1=*--it;
                if(seg1.r==p-1&&seg2.l==p+1)
                    erase(seg1), erase(seg2),
                    emplace(seg1.l, seg2.r);
                else if(seg1.r==p-1) erase(seg1), emplace(seg1.l, p);
                else if(seg2.l==p+1) erase(seg2), emplace(p, seg2.r);
                else emplace(p, p);
            }
        }
    }
}

标签:node,emplace,插排,int,题解,void,TJOI2014,itv,return
From: https://www.cnblogs.com/redacted-area/p/18405331

相关文章

  • CF1621G Weighted Increasing Subsequences 题解
    题目链接点击打开链接题目解法这种题就感觉每一步都不难想,但串在一起就不会显然考虑位置\(x\)作为\(lis\)的一部分,合法的\(lis\)的个数合法的约束是:令\(lis\)的最后一个位置为\(last\),满足\(\max\{a_{last+1},...,a_n\}>a_x\)不难发现,合法的\(last\)是一段区间......
  • 【最新华为OD机试E卷-支持在线评测】通过软盘拷贝文件(200分)多语言题解-(Python/C/Ja
    ......
  • P7230 题解
    P7230思路对每个左端点维护右端点\(res_i\)。操作形如删去一个数再加入一个数。如果删掉\(p\)上的\(a_p\),找到左右最近的\(l,r\)使得\(a_l=a_r=a_p\)。那么\(res_{l+1},\dotsb,res_p\)对\(r\)取max。实际上要维护\(\maxres_i-i+1\),因为\(res_i\)单调,所以相当于......
  • 【题解】Solution Set - NOIP2024集训Day25 概率期望 dp
    【题解】SolutionSet-NOIP2024集训Day25概率期望dphttps://www.becoder.com.cn/contest/5515「QOJ2606」Gachapon\(f_{i,j}\):用一次合法的level-irolling能够抽到的\(j\)的期望个数。\(h_{i,j,k}\):在\(i\)次操作之内,抽到恰好\(k\)个\(j\)的概率。\[h_{i,j,k......
  • luogu4198题解
    随机说话这个题做法没见过记一下。我一开始以为是李超树的题,结果把李超树打上之后就不会做了。然后题读错了写了一个弱化版。题目分析做法参考这个题题意只是假装是一个有关线段的题。简化之后的题意如下。有一个初始都为\(0\)的实数数列,每一次会修改位置\(x\)的数为......
  • Flutter 3.24 构建 release 抛出部分依赖 AAPT: error: resource android:attr/lStar
    问题截图:一些讨论:https://github.com/transistorsoft/flutter_background_fetch/issues/369问题原因及解决方案:@Aziz-T该问题与插件的compileSdkVersion和targetSdkVersion有关。出现该问题的原因是部分插件的compileSdkVersion和targetSdkVersion版本过旧。请前往......
  • P2471 [SCOI2007] 降雨量 题解
    题目传送门分析分讨题。首先发现是RMQ问题(区间最值),可以用线段树或ST表来维护(代码为线段树,因为我忘记ST表怎么写了)。然后发现有些年份不明确导致区间判断似乎不好搞。但事实上只要判断下标差是否等于年份差即可得出该区间有无不明确年份。其次考虑“必真”,“必假”,“......
  • 【洛谷 P1996】约瑟夫问题 题解(数组+模拟+循环)
    约瑟夫问题题目描述个人围成一圈,从第一个人开始报数,数到的人出列,再由下一个人重新从开始报数,数到的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。注意:本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰名小朋友,而该题是全部出圈。输入......
  • 题解 GZOI2023D2B【乒乓球】
    4s,512M题目描述Alice和Bob在打乒乓球,乒乓球比赛的规则是这样的:一场比赛中两位选手将进行若干局比赛,选手只需要赢得\(X\)局比赛就宣告其胜利;每局比赛中两位选手将进行若干盘比赛,选手只需要赢得\(Y\)盘比赛就宣告其胜利;每盘比赛中两位选手将进行乒乓球对决,有且仅有一位选......
  • AtCoder Beginner Contest 274 A~E 题解
    吐槽:这比赛名字为啥没有英文版。。。A-BattingAverage题目大意给定整数\(A,B\),输出\(\fracBA\),保留三位小数。\(1\leA\le10\)\(0\leB\leA\)分析签到题,使用printf或cout格式化输出即可。代码#include<cstdio>usingnamespacestd;intmain(){ inta,b; sc......