【Codeforces 643G】Choosing Ads

相关链接

题目传送门：http://codeforces.com/problemset/problem/643/G
官方题解：http://codeforces.com/blog/entry/44754

解题报告

先让我们来看一个简单版本：

限制空间，不让你开数组
如何找出在一个序列中出现次数超过一半的数
题目来源：BZOJ 2456

似乎除了排序就没有其他方式了？
但考虑将不相同的数两两抵消
剩下的就一定是我们要求的那个数

现在回到原题：

出现频率超过 $ p\%$

那岂不是每次将 $ \frac{{100}}{p}$ 个不同的数两两抵消
剩下的就是我们要求的数了？
这样的话，一个区间的信息我们只需要 $ \frac{{100}}{p}$的空间就可以保存啦！
于是剩下的就是线段树的锅辣！

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 150000 + 9;
const int M = N << 1;
const int L = 6;

int n,m,p,STA,val[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

class Segment_Tree{
	int cnt,root,ch[M][2],tag[M],len[M],ans;
	struct Data{int x,y;}sum[M][L],vout[L];
	public:
		inline void init() {
			for (int i=1;i<=n;i++)
				modify(i, i, val[i]);
		}
		inline void modify(int l, int r, int v) {
			modify(root, 1, n, l, r, v);
		}
		inline void query(int l, int r) {
			ans = 0;
			query(root, 1, n, l, r);
			printf("%d ",ans);
			for (int i=1;i<=ans;i++) 
				printf("%d ",vout[i]);
			putchar('\n');	
		}
	private:
		inline void maintain(Data *a1, int &l1, Data *a2, int l2, Data *a3, int l3) {
			static Data ret[L];
			memcpy(ret, a2, sizeof(ret));
			for (int i=1,tag=0;i<=l3;i++,tag=0) {
				for (int j=1;j<=l2;j++) {
					if (ret[j].x == a3[i].x) {
						ret[j].y += a3[i].y;
						tag = 1; break;
					}
				}
				if (!tag) ret[++l2] = a3[i];
			}
			if (l2 > STA) {
				sort(ret+1, ret+1+l2, [](const Data &A, const Data &B){return A.y>B.y;});
				for (int i=l2;i>STA;i--) {
					for (int j=1;j<i;j++) {
						ret[j].y -= ret[i].y;
					} 
				}
				l2 = STA;
			}
			while (ret[l2].y <= 0) l2--; 
			memcpy(a1, ret, sizeof(ret));
			l1 = max(0, l2);
		}
		inline void push_down(int w, int l, int r, int mid) {
			modify(ch[w][0], l, mid-1, l, mid-1, tag[w]);
			modify(ch[w][1], mid, r, mid, r, tag[w]);
			tag[w] = 0;
		}
		void modify(int &w, int l, int r, int L, int R, int v) {
			if (!w) w = ++cnt;
			if (L <= l && r <= R) {
				tag[w] = v;
				len[w] = 1;
				sum[w][1].x = v;
				sum[w][1].y = r - l + 1;
			} else {
				int mid = l + r + 1 >> 1;
				if (tag[w]) push_down(w, l, r, mid);
				if (L < mid) modify(ch[w][0], l, mid-1, L, R, v);
				if (mid <= R) modify(ch[w][1], mid, r, L, R, v);
				int ls = ch[w][0], rs = ch[w][1];
				maintain(sum[w], len[w], sum[ls], len[ls], sum[rs], len[rs]);
			}
		}
		void query(int w, int l, int r, int L, int R) {
			if (!w) return;
			else if (L <= l && r <= R) {
				maintain(vout, ans, vout, ans, sum[w], len[w]);
			} else {
				int mid = l + r + 1 >> 1;
				if (tag[w]) push_down(w, l, r, mid);
				if (L < mid) query(ch[w][0], l, mid-1, L, R);
				if (mid <= R) query(ch[w][1], mid, r, L, R);
			}
		}
}SGT;

int main() {
	n = read(); m = read(); 
	p = read(); STA = 100 / p;
	for (int i=1;i<=n;i++) 
		val[i] = read();
	SGT.init();
	for (int i=1,l,r;i<=m;i++) {
		if (read() == 1) {
			l = read(); r = read();
			SGT.modify(l, r, read());
		} else {
			l = read(); r = read();
			SGT.query(l, r);
		}
	}
	return 0;
}