[模板]莫队/P3901 数列找不同

目录

[模板]莫队/P3901 数列找不同

题目

传送门

没有专门的模板,就把这道题作为模板啦

算法介绍

大致思想

听说这题有O(n)预处理,O(1)询问的方法,但是这不重要,还是先练练莫队吧

《算法竞赛 进阶指南》里面没有专门讲莫队,学得就有一丢丢麻烦

简单说,莫队就是

优雅的暴力

首先要注意:
莫队是离线算法

我们把询问分成t块(不一定十分精确,可能多出或缺少几个块,只是借用了分块的思想),任意一个块内,每一个询问的左端点和其它询问的左端点的差的绝对值不超过(sqrt n),且块内右端点升序排列.所以就有了进行stl sort的cmp函数:

bool cmp(node a , node b) {
	return (a.l / t != b.l / t) ? (a.l / t < b.l / t) : (a.r < b.r);
}
//在主函数中:t=sqrt(n)

t到这里就被已经抛弃了(毫无存在感)

对于排序后的每一个询问,我们抹去上一个询问的多出来的答案,并补充上一个询问没有的部分,得到当前询问的答案,为了方便,一般写成两个函数:

void add(int l , int r) {
	if(l == 0)++l;
	if(r < l)return;
	for(int i = l ; i <= r ; i++) {
        
	}
}
void earse(int l , int r) {
	if(l == 0)++l;
	if(r < l)return;
	for(int i = l ; i <= r ; i++) {
        
	}
}

莫队到这里就介绍完了,接下来看看时间复杂度:

时间复杂度

很显然,时间主要是花在了对询问的处理上,所以我们只讨论询问处理部分
分两种情况:

  1. 分块的第一个询问:由于块和块之间没有比较大的约定,add和earse两个操作都有可能要用到(O(n))的时间,又因为有(sqrt n)个块,所以时间复杂度为(O(nsqrt n))
  2. 其它情况:由于每一个块内右端点是递增的,所以一个块对右端点的处理总共用时(O(n)),又因为一共有(sqrt n)个块,所以处理右端点总共用时(O(nsqrt n)).对于左端点,由于分块内的左端点之差不超过(sqrt n),所以处理所有询问的左端点共用时(O(nsqrt n))(这里不单独讨论每一个块是因为块的长度不定,不如全部一起讨论更容易理解)

综上,时间复杂度为(O(nsqrt n))

代码

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define nn 100010
using namespace std;
int read() {
	int re = 0;
	char c = getchar();
	while(c < '0' || c > '9') c = getchar();
	while(c >= '0' && c <= '9')  
		re = (re << 1) + (re << 3) + c - '0',
		c = getchar();
	return re;
}
struct node{
	int l , r , id;
}ask[nn];
int t;
bool cmp(node a , node b) {
	return (a.l / t != b.l / t) ? (a.l / t < b.l / t) : (a.r < b.r);
}

int vis[nn];
int n , q;
int a[nn];
int check;
bool ans[nn];

void add(int l , int r) {
	if(l == 0)++l;
	if(r < l)return;
	for(int i = l ; i <= r ; i++) {
		++vis[a[i]];
		if(vis[a[i]] == 2)
			++check;
	}
}
void earse(int l , int r) {
	if(l == 0)++l;
	if(r < l)return;
	for(int i = l ; i <= r ; i++) {
		--vis[a[i]];
		if(vis[a[i]] == 1)
			--check;
	}
}
int main() {
	n = read() , q = read();
	for(int i = 1 ; i <= n ; i++)
		a[i] = read();
	
	for(int i = 1 ; i <= q ; i++) {
		ask[i].l = read() , ask[i].r = read() , ask[i].id = i;
	}
	t = sqrt(n);
	sort(ask + 1 , ask + q + 1 , cmp);
	
//	cout << endl;
//	for(int i = 1 ; i <= q ; i++)
//		cout << ask[i].l << ' ' << ask[i].r << endl;
//	return 0;
	for(int i = 1 ; i <= q ; i++) {
		earse(ask[i - 1].l , ask[i].l - 1);
		add(ask[i - 1].r + 1 , ask[i].r);
		
		earse(ask[i].r + 1 , ask[i - 1].r);
		add(ask[i].l , ask[i - 1].l - 1);
		ans[ask[i].id] = (check == 0);
		
	}
	for(int i = 1 ; i <= q ; i++)
		puts(ans[i] ? "Yes" : "No");
	return 0;
}

数据生成

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define nn 100010
using namespace std;
int read() {
	int re = 0;
	char c = getchar();
	while(c < '0' || c > '9') c = getchar();
	while(c >= '0' && c <= '9')  
		re = (re << 1) + (re << 3) + c - '0',
		c = getchar();
	return re;
}
struct node{
	int l , r , id;
}ask[nn];
int t;
bool cmp(node a , node b) {
	return (a.l / t != b.l / t) ? (a.l / t < b.l / t) : (a.r < b.r);
}

int vis[nn];
int n , q;
int a[nn];
int check;
bool ans[nn];

void add(int l , int r) {
	if(l == 0)++l;
	if(r < l)return;
	for(int i = l ; i <= r ; i++) {
		++vis[a[i]];
		if(vis[a[i]] == 2)
			++check;
	}
}
void earse(int l , int r) {
	if(l == 0)++l;
	if(r < l)return;
	for(int i = l ; i <= r ; i++) {
		--vis[a[i]];
		if(vis[a[i]] == 1)
			--check;
	}
}
int main() {
	n = read() , q = read();
	for(int i = 1 ; i <= n ; i++)
		a[i] = read();
	
	for(int i = 1 ; i <= q ; i++) {
		ask[i].l = read() , ask[i].r = read() , ask[i].id = i;
	}
	t = sqrt(n);
	sort(ask + 1 , ask + q + 1 , cmp);
	
//	cout << endl;
//	for(int i = 1 ; i <= q ; i++)
//		cout << ask[i].l << ' ' << ask[i].r << endl;
//	return 0;
	for(int i = 1 ; i <= q ; i++) {
		earse(ask[i - 1].l , ask[i].l - 1);
		add(ask[i - 1].r + 1 , ask[i].r);
		
		earse(ask[i].r + 1 , ask[i - 1].r);
		add(ask[i].l , ask[i - 1].l - 1);
		ans[ask[i].id] = (check == 0);
		
	}
	for(int i = 1 ; i <= q ; i++)
		puts(ans[i] ? "Yes" : "No");
	return 0;
}

对拍

#include <bits/stdc++.h>
using namespace std;
int main() {
	int cnt = 0;
	while(true) {
		++cnt;
		putchar('
');
		printf("#%d
" , cnt);
		
		system("random.exe > input.txt");
		puts("random");
		
		int t = clock();
		if(system("tested2.exe < input.txt > output1.txt") != 0) {
			cout << "RE";
			break;
		}
		puts("tested2");
		t = clock() - t;
		printf(">time: %d
" , t);
		if(t >= 1500) {
			cout << "TLE";
			break;
		}
		
		continue;
		
		system("std.exe < input.txt > output2.txt");
		puts("std");
		
		if(system("fc output1.txt output2.txt")) {
			cout << "WA";
			break;
		}
	}
	system("start input.txt");
	return 0;
}

暴力

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define nn 100010
using namespace std;
int read() {
	int re = 0;
	char c = getchar();
	while(c < '0' || c > '9') c = getchar();
	while(c >= '0' && c <= '9')  
		re = (re << 1) + (re << 3) + c - '0',
		c = getchar();
	return re;
}
int vis[nn];
int a[nn];
int n , q;
int main() {
	n = read(), q = read();
	for(int i = 1 ; i <= n ; i++)
		a[i] = read();
	
	for(int i = 1 ; i <= q ; i++) {
		memset(vis , 0 , sizeof(vis));
		int l = read() , r = read();
		for(int j = l ; j <= r ; j++)
			vis[a[j]]++;
		
		bool check = true;
		for(int j = l ; j <= r && check ; j++)
			if(vis[a[j]] > 1)
				check = false;
		puts(check ? "Yes" : "No");
	}
	return 0;
}

50分(TLE)莫队(我也不知道哪里有问题)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define nn 100010
using namespace std;
int read() {
	int re = 0;
	char c = getchar();
	while(c < '0' || c > '9') c = getchar();
	while(c >= '0' && c <= '9')  
		re = (re << 1) + (re << 3) + c - '0',
		c = getchar();
	return re;
}
int vis[nn];
int a[nn];
int n , q;

struct QueryNode {
	int l , r;
	int id;
}ask[nn];
bool cmp0(QueryNode a , QueryNode b){return a.l < b.l;}
bool cmp1(QueryNode a , QueryNode b){return a.r < b.r;}
int ans[nn];

int t;
int L[110] , R[110];
int main() {
	n = read(), q = read();
	for(int i = 1 ; i <= n ; i++)
		a[i] = read();
	for(int i = 1 ; i <= q ; i++)
		ask[i].l = read() , ask[i].r = read() , ask[i].id = i;
	
	t = sqrt(q);
	R[0] = 0;
	for(int i = 1 ; i <= t ; i++)
		L[i] = R[i - 1] + 1 , R[i] = i * (q / t);
	if(R[t] < q)	t++ , L[t] = R[t - 1] + 1 , R[t] = q;
	
	sort(ask + 1 , ask + q + 1 , cmp0);
	for(int i = 1 ; i <= t ; i++)
		sort(ask + L[i] , ask + R[i] + 1 , cmp1);
	
//	for(int i = 1 ; i <= q ; i++)
//		cout << ask[i].l << ' ' << ask[i].r << endl;
	
	for(int i = 1 ; i <= t ; i++) {
		memset(vis , 0 , sizeof(vis));
		int check = 0;
		for(int j = ask[L[i]].l ; j <= ask[L[i]].r ; j++) {
			++vis[a[j]];
			if(vis[a[j]] == 2)
				++check;
		}
		ans[ask[L[i]].id] = (check == 0 ? true : false);
		
		
		for(int j = L[i] + 1 ; j <= R[i] ; j++) {
			if(ask[j - 1].l < ask[j].l)
				for(int k = ask[j - 1].l ; k < ask[j].l ; k++) {
					--vis[a[k]];
					if(vis[a[k]] == 1)
						check--;
				}
			else 
				for(int k = ask[j].l ; k < ask[j - 1].l ; k++) {
					++vis[a[k]];
					if(vis[a[k]] == 2)
						check++;
				}
				
			
			for(int k = ask[j - 1].r + 1 ; k <= ask[j].r ; k++) {
				++vis[a[k]];
				if(vis[a[k]] == 2)
					check++;
			}
			/*
			check = 0;
			for(int k = ask[j].l ; k <= ask[j].r ; k++)
				if(vis[a[k]] > 1)
					check++;*/
			ans[ask[j].id] = (check == 0 ? true : false);
		}
	}
	for(int i = 1 ; i <= q ; i++)
		puts(ans[i] ? "Yes" : "No");
	return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/dream1024/p/14050067.html