首页 > 其他分享 >P1503 鬼子进村 题解

P1503 鬼子进村 题解

时间:2024-03-07 13:24:36浏览次数:22  
标签:P1503 进村 mathit int 题解 cnt len ans block

分析

分块。

我们定义 \(\mathit{cnt}_i\) 表示房子 \(i\) 是否出现过,\(\mathit{sum}_i\) 表示在第 \(i\) 个块内没有被摧毁的房子数量,维护的房子是 \((i-1)\times S-1\) 到 \(i \times S\),其中 \(S=\sqrt{n}\) 也就是块长。

操作 \(1\)。写一个栈,根据后进先出的特点,讲摧毁的房子 \(x\) 入栈,以便后面修复。将 \(\mathit{cnt}_x\) 与 \(x\) 对应块的 \(\mathit{sum}\) 减 \(1\) 即可。

操作 \(2\)。先从栈里找到被修复的房子 \(x\)。与操作 \(1\) 同理,将减 \(1\) 变成加 \(1\) 即可。

操作 \(3\)。对于 \(x\) 能走到的房子,一定是在 \([l,r]\) 满足 \(\sum\limits_{i=l}^r \mathit{cnt}_i =(r-l+1)\) 的情况下的最大区间。我们可以分开来求。对于暴力,我们从 \(x\) 开始一直走,直到某一个 \(\mathit{cnt}_i=0\) 为止,能证明这是最大区间的 \(l\)。\(r\) 同理,不在此赘述。考虑优化,我们可以先找到 \(x\) 所在的块 \(k_x\),暴力求 \(k_x\) 中的贡献,再对于整块求贡献,最后对于不完整的块(答案边界)暴力。这里需要特别对 \(k_x=k_n\) 进行判断,因为 \(k_n \times S\) 可能大于 \(n\),即最后一个块不完整。这时候直接暴力。由于我们是分开求 \(l,r\) 两边的贡献的,这时候在 \(\mathit{cnt}_x=1\) 的情况会将 \(x\) 的贡献重复加 \(1\) 遍,所以要对贡献和减 \(1\)。

复杂度是 \(O(n\sqrt{n})\) 的。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline

const int N=5e4+10;
int cnt[N],sum[N],block,len;
int n,m;
int st[N],tt;

il int get(int x){return (x-1)/len+1;}
il int findl(int x){
	block=get(x);
	int ans=0;
	for(re int i=x;i>=((block-1)*len)+1;--i)
		if(!cnt[i]) return ans;
		else ans++;
	--block;
	for(;block>=1;--block)
		if(sum[block]==len) ans+=len;
		else for(re int i=block*len;i>=((block-1)*len)+1;--i)
			if(!cnt[i]) return ans;
			else ans++;
	return ans;
}
il int findr(int x){
	int maxx=get(n);
	block=get(x);
	int ans=0;
	for(re int i=x;i<=block*len&&i<=n;++i)
		if(!cnt[i]) return ans;
		else ans++;
	++block;
	for(;block<maxx;++block)
		if(sum[block]==len) ans+=len;
		else for(re int i=(block-1)*len+1;i<=block*len;++i)
			if(!cnt[i]) return ans;
			else ans++;
	for(re int i=(block-1)*len+1;i<=n;++i)
		if(!cnt[i]) return ans;
		else ans++;
	return ans;
}

il void solve(){
	cin>>n>>m;len=sqrt(n);
	for(re int i=1;i<=n;++i) ++cnt[i],++sum[get(i)];
	for(re int i=1;i<=m;++i){
		char op;int x,now;cin>>op;
		if(op=='D') cin>>x,st[++tt]=x,--cnt[x],--sum[get(x)];
		else if(op=='R') now=st[tt--],++cnt[now],++sum[get(now)];
		else cin>>x,cout<<((!cnt[x])?0:findl(x)+findr(x)-1)<<"\n";
	}
	return ;
}

signed main(){
	solve();
	return 0;
}

标签:P1503,进村,mathit,int,题解,cnt,len,ans,block
From: https://www.cnblogs.com/harmisyz/p/18058680

相关文章

  • ARC090E 题解
    Solution一道不错的计数题。因为直接求不相遇的方案十分复杂,所以考虑正难则反,用总的方案数减去相遇的方案数。求方案数很套路:在求最短路的时候开一个数组\(del\)记录到达点\(i\)的最短路条数,更新最短路时顺便更新即可。跑完最短路后,设\(dis1\)为\(s\)到\(t\)的最短路......
  • AT_abc256_h [ABC256Ex] I like Query Problem 题解
    分析用势能线段树。对于一段数字\(a_l\)到\(a_r\),每次全部除以一个大于\(1\)的数,不难发现最多除以\(\logx\)次就会使\(a_l\)到\(a_r\)全部变成\(0\),其中\(x\)是区间最大值。所以,在没有操作\(2\)的情况下,我们可以在每次操作\(1\)的时候都单点修改,只要在某个......
  • CF1070C Cloud Computing 题解
    分析思路不难想,我们对于第\(i\)个计划的时间,可以分成\(l\)和\(r+1\)两部分。用权值线段树维护,在第\(l\)天的时候就将该计划的内容加入权值线段树中,直到过了该计划的时间,也就是第\(r+1\)天,再将这个计划的内容删除。把每一天需要修改的内容存进vector中,修改完查询权值......
  • AT_dwacon5th_prelims_c k-DMC 题解
    分析先考虑\(k=n\)的情况。对于\(s_j=M\)的时候,其能够匹配的\(s_i=D\)的数量很显然是\(i\lej-1\)的时候的数量,求前缀和就能得到。而对于\(s_j=C\)的时候,能够完整匹配的就是\(i\lej-1\)的时候所有\(s_i=M\)能够匹配的数量之和,再套个前缀和就行了。复杂度是\(O......
  • CF1899G Unusual Entertainment 题解
    分析一眼树上启发式合并。定义\(x_i\)为节点\(i\)在序列\(p\)中的下标。则问题转化为:对于每组\(l,r,k\),询问以\(k\)为根的子树中是否有一个以上的节点,满足\(l\lex_j\ler\)。使用set存以\(i\)为根的子树中\(x_j\)的有序排列。则对于每个\(k=i\)的询问,去合......
  • AT_abc328_f [ABC328F] Good Set Query 题解
    分析考虑并查集。对于\(a_i,b_i,d_i\),若\(a_i,b_i\)在之前的满足要求的操作中,\(a_i,b_i\)不在同一个集合里,则在之前\(X_{a_i},X_{b_i}\)的相对差值是可以任意改变的。令\(k=X_{a_i}-X_{b_i}\),则我们需要将\(a_i\)所在集合中所有元素的值增加\(d_i-k\)。然后将\(a_i,b......
  • CF1895D XOR Construction 题解
    分析对于异或,有性质\(a\oplusb=c,a\oplusc=b,a\oplusa=0\)。则对于\(a_i\oplusa_{i+1}\),其表示的结果就是\(b_{i}\oplusb_{i+2}\)。做一个前缀异或和,就能够得到\(b_1\)与\(b_2,b_3,\dots,b_n\)的异或结果。考虑枚举\(b_1\),因为在有解的情况下\(b_1\op......
  • CF1896D 题解
    Solution令\(l,r\)能使\(\sum\limits_{i=l}^{r}a_i=S\)。考虑先令\(l=1\),那么如果存在\(\sum\limits_{i=1}^{r}=S\),即输出YES。如果没有,则一定有\(\sum\limits_{i=1}^{r}=S-1\),且\(a_{r+1}=2\)。考虑对\(l,r\)进行调整:将\(l\)向左移,\(r\)向右移。可以发现当\(......
  • AT_abc222_f [ABC222F] Expensive Expense 题解
    分析没脑子的题目。一眼换根DP。定义\(\mathit{f}_{i}\)表示\(i\)到\(i\)为根子树中某一个节点的距离最大值;\(\mathit{g}_{i}\)表示\(i\)经过其父节点到某个节点的距离最大值。那答案就是\(\max(\mathit{f}_i,\mathit{g}_i)\)。考虑转移。\(\mathit{f}_i\)的转移很......
  • CF1223F Stack Exterminable Arrays 题解
    分析接着这个说。现在我们需要优化\(\mathit{nxt}_{i}\)。重新定义一下,\(\mathit{nxt}_{i,j}\)表示在后\(i\)个数中,\(j\)第一次出现的位置,且\([i+1,\mathit{nxt}_{i+1,a_i}-1]\)是一个合法串。这玩意很像一个DP,所以完全可以按照DP的转移思路转移:\(\mathit{nxt}_{i,j}=......