正文

luogup1503鬼子进村(代码片段)

sdfzsyq  sdfzsyq  2023-01-01  771

关键词：

解题思路

平衡树，支持插入，删除，找前驱后继，set水过。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>

using namespace std;
const int MAXN = 50005;

inline int rd()
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) f=ch==‘-‘?0:1;ch=getchar();
    while(isdigit(ch))  x=(x<<1)+(x<<3)+ch-‘0‘;ch=getchar();
    return f?x:-x;


int n,m,stk[MAXN],top;
set<int> S;
set<int>::iterator it,it1;

int main()
    n=rd(),m=rd();char c;int x;
    S.insert(0),S.insert(n+1);
    while(m--)
        c=getchar();
        while(c<‘A‘ || c>‘Z‘) c=getchar();
        if(c==‘R‘) S.erase(stk[top]);top--;continue;
        x=rd();
        if(c==‘D‘) S.insert(x),stk[++top]=x;
        else
            if(S.find(x)!=S.end()) puts("0");continue;
            it=S.lower_bound(x);it1=it;it1--;
            printf("%d
",(*it)-(*it1)-1);
        
    
    return 0;

View Code

题解luogup1503鬼子进村(代码片段)

平衡树好题原题传送门这道题要用Splay，我博客里有对Splay的详细介绍这道题思维有点难，要把被摧毁的节点插入平衡树，而不是把没有摧毁的节点插入先把0和n+1插入平衡树，作为边界操作1：摧毁节点，把该点插入平衡树操作2... 查看详情

p1503鬼子进村(代码片段)

...亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。题目描述描述县城里有n个用地道相连的房子，第i个只与第i-1和第i+1个相连。这是有m个消息依次传来1、消息为Dx：鬼子将x号房... 查看详情

洛谷p1503鬼子进村

P1503鬼子进村题目背景小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。题目描述描述县城里有n个用地... 查看详情

洛谷——p1503鬼子进村

luogu1503(代码片段)

[洛谷1053]鬼子进村

luogup2042(代码片段)

luoguP2042主要是贴一下维护序列的板子：#include<bits/stdc++.h>usingnamespacestd;constintN=1000005;constintinf=1e8+1;constintNONE=1e9;#definels(x)(bst[x].ch[0])#definers(x)(bst[x].ch[1])#definegetKey(x)(bst[x]. 查看详情

1503.lastmomentbeforeallantsfalloutofaplank(代码片段)

Wehaveawooden plankofthelength n units.Someantsarewalkingonthe plank,eachantmoveswithspeed 1unitpersecond.Someoftheantsmovetothe left,theothermovetothe right.Whentwo 查看详情

luogup1401城市(代码片段)

题目链接luoguP1401城市题解二分最小边权,dinic检验代码//luogu-judger-enable-o2/*二分最小边权,dinic检验*/#include<queue>#include<cctype>#include<cstdio>#include<cstdlib>#include<cstring>#include<a 查看详情

luogup1663山(代码片段)

题目链接luoguP1663山题解只需要求出下凸包的最低点就好了显然是由两个斜率相反的直线相交来的盼下最低点为直线的情况代码#include<cstdio>#include<iostream>#include<algorithm>inlineintread()intx=0,f=1;charc=getchar();while(c<'0'... 查看详情

luogup1009阶乘之和(代码片段)

听说有人跟我比代码长……祭出祖传的高精度类型水一波……大概也就9k代码这样子……代码：#pragmaGCCoptinize(3)#pragmacomment(linker,"/STACK:102400000,10240000")#include<bits/stdc++.h>#defineLEN35663//100001usingnamespacestd;classB 查看详情

做题记录luogup2343(代码片段)

LuoguP2343宝石管理系统平衡树水题比treap模板还要弱#include<bits/stdc++.h>usingnamespacestd;#definemaxn80005*50classfhqtreap private: longlongch[maxn][2],size[maxn],rnd[maxn],val[maxn],tot; public: longlongcnt,ro 查看详情

luogup3959宝藏(代码片段)

题目链接luoguP3959宝藏题解开始写了个random_shuffle竟然水了70，然后退火一下就A了？每次做生成树的时候，随机两条边的顺序交换退火一下，就A了代码#include<cmath>#include<cstdio>#include<ctime>#include<cstring>#include<algor... 查看详情

luogup1439(代码片段)

#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;#defineN100011intn,w[N],a[N],f[N];intmain()memset(f,0x7f,sizeoff);f[0]=-1000;scanf("%d",&n);inttmp;for(inti 查看详情

次短路luogup2865(代码片段)

#include<cstdio>#include<cstring>#include<queue>usingnamespacestd;intn,r,head[1000005],dis1[1000005],dis2[1000005],vis[1000005],cnt;structedgeintv,w,next;e[1000005];structnodeintd 查看详情

luogup3369普通平衡树(代码片段)

luoguP3369主要是贴一个splay的模板：#include<bits/stdc++.h>usingnamespacestd;namespacesplay#definels(x)ch[x][0]#definers(x)ch[x][1]constintN=1000005;constintinf=2e9;intch[N][2],f[N],key[N],nums[N],sz[N];i 查看详情

luogup3413萌数(代码片段)

1#include<bits/stdc++.h>2usingnamespacestd;3constintmaxn=1e3+5;4constintmod=1e9+7;5intn,m,mark;6charl[maxn],r[maxn];7intnuml,numr;8inttot,e[maxn];9longlongc[maxn][20][2];10template<classt> 查看详情

luogup1084疫情控制(题解)(搜索+贪心)(代码片段)

luoguP1084疫情控制题目#include<iostream>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#defineilinline#definergregister#definelllongl 查看详情