【BZOJ】3809: Gty的二逼妹子序列

时间：2022-12-18 08:56:22

http://www.lydsy.com/JudgeOnline/problem.php?id=3809

题意：n个元素（1<=n<=100000）每个元素有一权值<=n。q个询问，1<=q<=1000000，每次询问区间[l, r]的权值在区间[a, b]的种类数。时限35s...

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

#include <set>

#include <map>

#include <sstream>

using namespace std;

typedef long long ll;

#define pb push_back

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << (#x) << " = " << (x) << endl

#define error(x) (!(x)?puts("error"):0)

#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)

inline int getint() { static int r, k; r=0,k=1; static char c; c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

const int N=100005;

int n, pos[N], cnt[N], sum[N], m, ans[N*10], w[N], sq;

struct dat { int l, r, a, b, id; }a[N*10];

inline bool cmp(const dat &a, const dat &b) { return pos[a.l]==pos[b.l]?a.r<b.r:a.l<b.l; }

void init() { sq=sqrt(n+0.5); for1(i, 1, n) pos[i]=(i-1)/sq+1; }

int ask(int l, int r) {

	int bl=pos[l], br=pos[r], ret=0;

	if(bl==br) { for1(i, l, r) ret+=cnt[i]>0; return ret; }

	for1(i, bl+1, br-1) ret+=sum[i];

	bl=sq*bl;

	br=sq*(br-1)+1;

	for1(i, l, bl) ret+=cnt[i]>0;

	for1(i, br, r) ret+=cnt[i]>0;

	return ret;

}

void update(int x, int k) {

	cnt[x]+=k;

	if(k==1 && cnt[x]==1) ++sum[pos[x]];

	if(k==-1 && cnt[x]==0) --sum[pos[x]];

}

int main() {

	read(n); read(m);

	for1(i, 1, n) read(w[i]);

	init();

	for1(i, 1, m) read(a[i].l), read(a[i].r), read(a[i].a), read(a[i].b), a[i].id=i;

	sort(a+1, a+1+m, cmp);

	int l=1, r=0;

	for1(i, 1, m) {

		int nl=a[i].l, nr=a[i].r;

		while(l<nl) update(w[l++], -1);

		while(l>nl) update(w[--l], 1);

		while(r<nr) update(w[++r], 1);

		while(r>nr) update(w[r--], -1);

		ans[a[i].id]=ask(a[i].a, a[i].b);

	}

	for1(i, 1, m) printf("%d\n", ans[i]);

	return 0;

}

　　

好神的一题orz

一开始写裸的线段树+莫队t了....没分析复杂度果然会跪...如果是这样写，单次查询$O(logn)$，修改$O(logn)$，而有$q$个询问，所以总的复杂度为$O(n^{1.5}logn+qlogn)$...tle成翔....单组极限数据大概就要5s以上的样子？

于是看题解，orz rausen orz hzwer

因为权值的范围在n内，我们可以将权值也分块！即统计对应块内的种类数即可...

这样的话，单次修改可以到$O(1)$，单次查询$O(n^{0.5})$，总的复杂度为$O(n^{1.5}+qn^{0.5})$，单组数据大概3s左右....

于是就水过了...

听说xyz大爷的集训队论文有更优越的做法，先留个坑...

相关文章