正文

luogup1503鬼子进村(代码片段)

mrclr  mrclr  2023-01-11  740

关键词：

嘟嘟嘟

线段树好题。

其实挺水的，想暴力怎么做：每一次从这个点开始向两边扩，直到遇到第一个摧毁的房屋。

那么把暴力改成倍增，然后线段树查询区间和是否为０。时间复杂度O(nlog²n)。

题解好像有线段树的O(nlogn)的做法，但是特别麻烦，也没怎么看懂。

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cmath>
  4 #include<algorithm>
  5 #include<cstring>
  6 #include<cstdlib>
  7 #include<cctype>
  8 #include<vector>
  9 #include<stack>
 10 #include<queue>
 11 using namespace std;
 12 #define enter puts("") 
 13 #define space putchar(‘ ‘)
 14 #define Mem(a, x) memset(a, x, sizeof(a))
 15 #define rg register
 16 typedef long long ll;
 17 typedef double db;
 18 const int INF = 0x3f3f3f3f;
 19 const db eps = 1e-8;
 20 const int maxn = 5e4 + 5;
 21 inline ll read()
 22 
 23   ll ans = 0;
 24   char ch = getchar(), last = ‘ ‘;
 25   while(!isdigit(ch)) last = ch; ch = getchar();
 26   while(isdigit(ch)) ans = ans * 10 + ch - ‘0‘; ch = getchar();
 27   if(last == ‘-‘) ans = -ans;
 28   return ans;
 29 
 30 inline void write(ll x)
 31 
 32   if(x < 0) x = -x, putchar(‘-‘);
 33   if(x >= 10) write(x / 10);
 34   putchar(x % 10 + ‘0‘);
 35 
 36 
 37 int n, m;
 38 char c[2];
 39 
 40 int l[maxn << 2], r[maxn << 2], sum[maxn << 2];
 41 void build(int L, int R, int now)
 42 
 43   l[now] = L; r[now] = R;
 44   if(L == R) return;
 45   int mid = (L + R) >> 1;
 46   build(L, mid, now << 1);
 47   build(mid + 1, R, now << 1 | 1);
 48 
 49 void update(int now, int id, int flg)
 50 
 51   if(l[now] == r[now]) sum[now] += flg; return;
 52   int mid = (l[now] + r[now]) >> 1;
 53   if(id <= mid) update(now << 1, id, flg);
 54   else update(now << 1 | 1, id, flg);
 55   sum[now] = sum[now << 1] + sum[now << 1 | 1];
 56 
 57 int query(int L, int R, int now)
 58 
 59   if(l[now] == L && r[now] == R) return sum[now];
 60   int mid = (l[now] + r[now]) >> 1;
 61   if(R <= mid) return query(L, R, now << 1);
 62   else if(L > mid) return query(L, R, now << 1 | 1);
 63   else return query(L, mid, now << 1) + query(mid + 1, R, now << 1 | 1);
 64 
 65 
 66 int solve(int x)
 67 
 68   if(query(x, x, 1)) return 0;
 69   int ret = 0;
 70   for(int t = x, i = 20; i >= 0; --i)
 71     
 72       int j = t + (1 << i) - 1;
 73       if(j > n) continue;
 74       if(!query(t, j, 1)) ret += (1 << i), t += (1 << i);
 75     
 76   for(int t = x, i = 20; i >= 0; --i)
 77     
 78       int j = t - (1 << i) + 1;
 79       if(j < 1) continue;
 80       if(!query(j, t, 1)) ret += (1 << i), t -= (1 << i);
 81     
 82   return ret - 1;
 83 
 84 
 85 int st[maxn], top = 0;
 86 
 87 int main()
 88 
 89   n = read(); m = read();
 90   build(1, n, 1);
 91   for(int i = 1; i <= m; ++i)
 92     
 93       scanf("%s", c);
 94       if(c[0] == ‘D‘)
 95     
 96       st[++top] = read();
 97       update(1, st[top], 1);
 98     
 99       else if(c[0] == ‘R‘) update(1, st[top--], -1);
100       else
101     
102       int x = read();
103       write(solve(x)), enter;
104     
105     
106   return 0;
107

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 查看详情