首页 > 其他分享 >记 Ynoi

记 Ynoi

时间：2024-08-08 19:16:23浏览次数：9  
标签：cnv cnt 分块 int 值域 Ynoi 100005

决定写写 Ynoi。

P4119 [Ynoi2018] 未来日记

最初分块。也是第一次品尝的 Ynoi 大分块。

1 l r x y 将 \([l, r]\) 区间内的 \(x\) 全部变成 \(y\)。

2 l r k 查询 \([l, r]\) 区间内的第 \(k\) 小值。

查询第 \(k\) 小看起来是个非常复杂的操作，一般来说看到这个想到的是二分、nth_element，或者值域树状数组上倍增、值域线段树上二分什么的。

这种看起来在区间上对值本身做什么事情的一般是分块，而分块跟 log 做法比较不搭，容易凭空生出一支 log 出来。更好的办法是直接值域分块。

将序列以块长 \(N\) 分块，值域以块长 \(V\) 分块。设 cnt[i][j] 表示前 \(i\) 块中有多少 \(j\)，cnv[i][j] 表示前 \(i\) 块中有多少数在 \(j\) 值域块中。

考虑 2 操作怎么做。有了这两个辅助数组就有个很显然的做法了。记辅助数组 tmc[], tmv[] 表示在当前询问区间有多少个 \(i\)、有多少个数在 \(i\) 值域块，将散块直接统计贡献，整块就用前面处理出来的东西记一下即可，最后从第一个值域块往后扫，让 \(k\) 减去统计值找到在哪个值域块中，再在这个值域块中扫一遍就行了，时间复杂度是根号的。

接下来考虑 1 操作怎么维护 cnt 和 cnv 数组。首先因为操作的数只有两个，操作的值域块的数量最多两个，所以可以先把 cnt 和 cnv 差分，还原成块内的计数，最后再前缀和回来。

注意到有很多时候整块修改时，把块内所有的 \(x\) 换成了一个原本块中没有的 \(y\)，那么 \(y\) 的 cnt 应该可以直接继承 \(x\) 的，而 cnv 也可以用 \(x\) 的 cnt 方便的修改，但是这样产生的问题是，无法实时记录真实值。

这启发我们建立一个映射数组，令块内的每个数和一个 \([1, \sqrt n]\) 的数一一对应（和离散化操作非常类似）。

设 id[i][j] 表示第 \(i\) 块中的 \(j\) 这个值被映射到了什么，rid[i][j] 为反数组，表示 \(i\) 块中的 \(j\) 代表什么数，tot[i] 表示第 \(i\) 块有多少个不同的数，pos[i] 表示 \(i\) 这个位置对应 \(i\) 所在的那一块中映射的哪个数。

有恒等式 rid[belong[i]][pos[i]] = a[i]。

那么整块的操作中，如果块内有 \(x\) 无 \(y\) 就能通过修改映射 \(O(1)\) 解决了。

考虑别的情况。首先散块操作，可以直接暴力改，然后再暴力重构映射，因为是散块，怎么操作都是一支根号的。整块操作中如果没有 \(x\) 跳过就是了。

考虑整块操作中同时有 \(x\) 和 \(y\) 的地方。在这里，我们只用暴力修改后重构这一块就行了。

这样的时间复杂度为什么是对的呢？考虑数字种类数。一开始数字最多是 \(n\) 种，而只有对散块修改的时候才可能产生新的数字，所以最后数字种类是 \(O(n + m)\) 级别的。而在同时有 \(x\) 和 \(y\) 的块，数字种类会减少一种。暴力重构的复杂度是 \(\sqrt n\)，所以重构块的总复杂度就是 \(O((n + m)\sqrt n)\) 的，是没问题的。

然后你会发现这么多复杂的操作每一步的复杂度都是 \(\sqrt n\) 或者 \(\sqrt v\) 的，其中 \(v\) 是值域。因为 \(n, m\) 与 \(v\) 同级，所以时间复杂度是 \(O(n \sqrt n)\)。

但是这题卡常，所以要注意一些细节和剪枝。我特判了两种情况。第一种是如果区间查询所涉及的块内没有 \(x\) 那这次修改操作就忽略掉，二是如果散块中没有出现 \(x\) 就可以不用重构。

还有就是把块长 \(N\) 和 \(V\) 开成常量对常数优化很大。

然后就过了。细节其实很多，每天做白天的题外抽空写写调调花了一周。

#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cmath>
//#define int long long
//#define DEBUG
using namespace std;
const int P = 1e9 + 7, inf = 0x3f3f3f3f;
using pii = pair<int, int>;
namespace azus{
	int n, Q;
	const int N = 300, V = 250;
	const int vl = 450;
	int bl;
	int a[100005];
	int Cnt;
	int belong[100005], L[100005], R[100005];
	int cnt[505][100005], cnv[505][50005]; //前 i 个块中 v 有多少个、前 i 个块中在 v 块中的数有多少个。
	int id[505][100005], rid[505][705], pos[100005], tot[505];
	int gbx, gby;
	int build(){
		
#ifdef DEBUG
		N = 15, V = 15;
#endif
#ifndef DEBUG
//		N = 300, V = 250;
#endif
#define gb(i) ((i - 1) / V + 1)
		bl = n / N;
		if(n % N != 0)
			bl ++;
		for(int i = 1; i <= bl; i ++){
			L[i] = (i - 1) * N + 1, R[i] = min(n, i * N);
			for(int j = L[i]; j <= R[i]; j ++){
				belong[j] = i;
				cnt[i][a[j]] ++, cnv[i][gb(a[j])] ++;
				if(cnt[i][a[j]] == 1){
					tot[i] ++;
					pos[j] = tot[i];
					rid[i][tot[i]] = a[j];
					id[i][a[j]] = tot[i];
				} else{
					pos[j] = id[i][a[j]];
				}
			}
			for(int j = 1; j <= 100000; j ++)
				cnt[i][j] += cnt[i - 1][j];
			for(int j = 1; j <= vl; j ++)
				cnv[i][j] += cnv[i - 1][j];
		}	
		return 0;
	}
	int tmpc[100005], tmpv[705];
	int restruct(int u){ 
		tot[u] = 0;
		for(int i = L[u]; i <= R[u]; i ++){
			tmpc[a[i]] ++, tmpv[gb(a[i])] ++;
			if(tmpc[a[i]] == 1){
				tot[u] ++;
				pos[i] = tot[u];
				id[u][a[i]] = tot[u];
				rid[u][tot[u]] = a[i];
			} else {
				pos[i] = id[u][a[i]];
			}
		}
		for(int i = L[u]; i <= R[u]; i ++)
			tmpc[a[i]] --, tmpv[gb(a[i])] --;
		return 0;
	}
	int modify(int l, int r, int x, int y){
		if(x == y) return 0;
		gbx = gb(x), gby = gb(y);
		int u = belong[l], v = belong[r];
		if(cnt[v][x] == cnt[u - 1][x]) return 0;
		for(int i = bl; i >= u; i --){
			cnt[i][x] -= cnt[i - 1][x], cnt[i][y] -= cnt[i - 1][y];
			if(gbx != gby)
				cnv[i][gbx] -= cnv[i - 1][gbx], cnv[i][gby] -= cnv[i - 1][gby];
			else cnv[i][gbx] -= cnv[i - 1][gbx];
		}
		for(int i = L[u]; i <= R[u]; i ++)
			a[i] = rid[u][pos[i]];
		if(v != u) for(int i = L[v]; i <= R[v]; i ++)
			a[i] = rid[v][pos[i]];
		if(u == v){
			for(int i = l; i <= r; i ++)
				if(a[i] == x) cnt[u][a[i]] --, cnv[u][gbx] --, a[i] = y, cnt[u][a[i]] ++, cnv[u][gby] ++;
			restruct(u);
			for(int i = u; i <= bl; i ++){
				cnt[i][x] += cnt[i - 1][x], cnt[i][y] += cnt[i - 1][y];
				if(gbx != gby)
					cnv[i][gbx] += cnv[i - 1][gbx], cnv[i][gby] += cnv[i - 1][gby];
				else cnv[i][gbx] += cnv[i - 1][gbx];
			}
			return 0;
		}
		if(cnt[u][x] != 0){
			for(int i = l; i <= R[u]; i ++)
				if(a[i] == x) cnt[u][a[i]] --, cnv[u][gbx] --, a[i] = y, cnt[u][a[i]] ++, cnv[u][gby] ++;
			restruct(u);} if(cnt[v][x] != 0){
				for(int i = L[v]; i <= r; i ++)
					if(a[i] == x) cnt[v][a[i]] --, cnv[v][gbx] --, a[i] = y, cnt[v][a[i]] ++, cnv[v][gby] ++;
				restruct(v);}
		for(int i = u + 1; i < v; i ++){
			if(cnt[i][x] == 0) continue;
			if(cnt[i][y] == 0){
				rid[i][id[i][x]] = y;
				id[i][y] = id[i][x], id[i][x] = 0;
				cnv[i][gby] += cnt[i][x], cnv[i][gbx] -= cnt[i][x];
				cnt[i][y] = cnt[i][x], cnt[i][x] = 0;
				continue;
			}
			for(int j = L[i]; j <= R[i]; j ++){
				a[j] = rid[i][pos[j]];
				if(a[j] == x) cnt[i][a[j]] --, cnv[i][gbx] --, a[j] = y, cnt[i][a[j]] ++, cnv[i][gby] ++;
			}
			restruct(i);
		}
		for(int i = u; i <= bl; i ++){
			cnt[i][x] += cnt[i - 1][x], cnt[i][y] += cnt[i - 1][y];
			if(gbx != gby)
				cnv[i][gbx] += cnv[i - 1][gbx], cnv[i][gby] += cnv[i - 1][gby];
			else cnv[i][gbx] += cnv[i - 1][gbx];
		}
		return 0;
	}
	int query(int l, int r, int k){
		int u = belong[l], v = belong[r];
		if(u == v){
			for(int i = l; i <= r; i ++){
				int val = rid[u][pos[i]];
				tmpc[val] ++, tmpv[gb(val)] ++;
			}
		}
		else{
			for(int i = l; i <= R[u]; i ++){
				int val = rid[u][pos[i]];
				tmpc[val] ++, tmpv[gb(val)] ++;
			}
			for(int i = L[v]; i <= r; i ++){
				int val = rid[v][pos[i]];
				tmpc[val] ++, tmpv[gb(val)] ++;
			}
		}
		int poss = -1;
		for(int i = 1; i <= vl; i ++){
			if(u != v) tmpv[i] += (cnv[v - 1][i] - cnv[u][i]);
			if(k - tmpv[i] <= 0) {
				poss = i;
				break;
			}
			k -= tmpv[i];
		}
		int ans = -1;
		for(int i = (poss - 1) * V + 1; i <= poss * V; i ++){
			if(u != v) tmpc[i] += (cnt[v - 1][i] - cnt[u][i]);
			if(k - tmpc[i] <= 0){
				ans = i;
				break;
			}
			k -= tmpc[i];
		}
		for(int i = (poss - 1) * V + 1; i <= ans; i ++)
			tmpc[i] = 0;
		for(int i = 1; i <= poss; i ++)
			tmpv[i] = 0;
		for(int i = l; i <= R[u]; i ++)
			tmpc[rid[u][pos[i]]] = 0, tmpv[gb(rid[u][pos[i]])] = 0;
		for(int i = L[v]; i <= r; i ++)
			tmpc[rid[v][pos[i]]] = 0, tmpv[gb(rid[v][pos[i]])] = 0;
		return ans;
	}
	int main(){
		cin >> n >> Q;
		for(int i = 1; i <= n; i ++)
			cin >> a[i];
		build();
		while(Q --){
			int opt = 0;
			cin >> opt;
			if(opt == 1){
				int l, r, x, y;
				cin >> l >> r >> x >> y;
				modify(l, r, x, y);
			} else {
				int l, r, k;
				cin >> l >> r >> k;
				cout << query(l, r, k) << "\n";
			}
		}
		return 0;
	}
}
signed main(){
#ifndef DEBUG
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#endif
	int T = 1;
	while(T --)
		azus::main();
	return 0;
}

标签：cnv,cnt,分块,int,值域,Ynoi,100005
From： https://www.cnblogs.com/AzusidNya/p/18349565

相关文章

  • P9058 [Ynoi2004] rpmtdq 与 P9678 [ICPC2022 Jinan R] Tree Distance
    思路：注意到点对数量有\(N^2\)个，考虑丢掉一些无用的点对。对于点对\((x_1,y_1),(x_2,y_2)\)，满足\(x_1\lex_2<y_2\ley_1\)，即区间\([x_2,y_2]\)被\([x_1,y_1]\)包含，此时满足若询问到了\([x_1,y_1]\)，则一定会询问到\([x_2,y_2]\)。若满足\(\operatorname{dis}(x_1......
  • G73 线段树+线性基合并 P5607 [Ynoi2013] 无力回天 NOI2017
    视频链接：G73线段树+线性基合并P5607[Ynoi2013]无力回天NOI2017_哔哩哔哩_bilibili   P5607[Ynoi2013]无力回天NOI2017-洛谷|计算机科学教育新生态(luogu.com.cn)//线段树+线性基合并O(n*logn*logv*logv)#include<iostream>#include<cstring>#incl......
  • P9058 [Ynoi2004] rpmtdq
    前言开个巨坑，可能以后会三四天一更？分析路径考虑点分治，以下的\(dis\)皆为确定根节点的。以下点对\((i,j)\)都钦定\(dis_i\ledis_j\)注意到很多点对对答案是无用的，条件为若点对\((i,j)\)存在\(k\in[l+1,r-1]\)，满足\(dis_i>=dis_k\or\dis_j\gedis_k\)，则点对\((i,j)......
  • P4688 Ynoi2016 掉进兔子洞
    P4688Ynoi2016掉进兔子洞经典莫队加bitset。思路不难发现最终答案就是：\[(r_1-l_1+1)+(r_2-l_2+1)+(r_3-l_3+1)-3\timessize\]其中\(size\)表示3个区间内出现了多少个公共元素。看到这么多区间，不妨有把区间拆下来搞莫队的想法。先不考虑询问个数的限制，我们考虑使用......
  • YC307B [ 20240625 CQYC省选模拟赛 T2 ] 一个题（ynoi）
    题意你需要维护一个可重集\(S\)，支持插入删除以及查询最大的方案使得给定正整数\(k\)，划分为\(k\)个非空子集的按位与结果之和最大。\(n\le10^5\)Sol先上个trie。然后考虑一次查询怎么搞。先转化一下，如果需要划分为\(k\)个子集，显然需要合并\(n-k\)次。我们只......
  • P5311 [Ynoi2011] 成都七中
    题目描述给你一棵\(n\)个节点的树，每个节点有一种颜色，有\(m\)次查询操作。查询操作给定参数\(l\r\x\)，需输出：将树中编号在\([l,r]\)内的所有节点保留，\(x\)所在连通块中颜色种类数。每次查询操作独立。对于\(100\%\)的数据，所有出现过的数在\([1,10^5]\)之间，保证每......
  • P9999 [Ynoi2000] tmostnrq 题解
    巨大难写题。就这样一个毒瘤的题，还有人把时空缩小成二分之一放在模拟赛，太好笑了。思路首先将询问离线。我们在\(l_i\)处加入这个点，在\(r_i\)处查询这个点在哪里。那么我们就需要有一个数据结构支持让所有树上的节点一起动。考虑所有点往\(x\)处动。那么对于在\(1\si......
  • P6781 [Ynoi2008] rupq
    P6781[Ynoi2008]rupq线段树上维护这种括号序列，如果信息可差分是好做的，但现在只能合并。先说如何合并信息。max是简单的。至于nand，不需要考虑结合律，只要维护一个bool[32][2]表示当某一位的第一个操作数是0/1时，经过它们的传递、运算的结果是什么。见于P2114[NOI2014]......
  • Ynoi 做题记录
    [Ynoi2011]初始化第一道通过的Ynoi题，虽然似乎大概也许并不太难。题目分析查询操作为求区间和，可以使用分块。看到这种修改操作满足“跳着加”性质的题目，可以尝试根号分治。那么如何进行根号分治呢？当\(x\ge\sqrt{n}\)时，需要修改的位置最多有\(\sqrt{n}\)个，故可以暴力......
  • [Ynoi2015] 纵使日薄西山
    按照题目来模拟，假设\(a_x\)为最大的，那么任意时刻不可能选中\(a_{x-1}\)或者\(a_{x+1}\)来操作的然后就可以发现，我们选出的数一定是不相邻的，也就是说，我们每次在还可以选择的数中找出最大的数（满足此条件下下标最小），并且把相邻的两个数标记为不可选择，一直重复这个过程直到为\(0\)；显然......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99