[SPOJ QTREE] Link Cut Tree引发的血案

最近在整理5月份和老毛子5V5的模板,发觉自己以前的LCT简直是圡得无法直视……
于是把wjmzbmr大大的模板down下来观摩了一番,写了个QTREE。原以为很快搞定的,没想到TLE到死。
上网找了一些LCT的代码交上去,发现都挺慢的……于是继续改,陆陆续续地加了点常数优化全都不顶事。最后不知道哪根筋抽了居然会想起在每个函数前加一个inline,然后它就过了……
原来根本原因是坑爹的SPOJ没有开O2 = =b
好在在搜集代码的过程中学习了好多新姿势,于是我的Splay模板又可以继续改进了。算是忙乎一晚上的一点成果吧。

Qtree
[传送门]
[Code]

感觉这个写法还是挺舒服的,于是以后就用这好了。
有空把剩下的QTREE再刷刷完吧~扎实点总没错的

update@2013.3.28 17:00

Qtree2
[传送门]
[Code]

感觉这个LCT写得姿势更好了……

Qtree3
[传送门]
[Code]

……和Qtree2没啥区别,改改就过了。注意一下范围大了10倍就好。

[icpcarchive 6045 – Alien Abduction] Scapegoat Tree + KD Tree

今年雅加达的H题。OJ上一直没人过,然后自己写了一下,线段树套set TLE了几回,然后想起之前一直没敢写的Scapegoat Tree + KD Tree,试了一下居然AC了。
^_^哈哈,不得不说,这种拿题库FirstBlood的感觉真是爽。
传送门
【题意】

给定n(n<=50000)个在二维平面上的整点,坐标保证0<=x<=w, 0<=y<=h。再给定q(q<=50000)个操作,每个操作为给定一个点$$(x_i, y_i)$$,将离$$(x_i, y_i)$$曼哈顿距离小于等于$$E_i$$的点的坐标都作一个奇葩的变换。 $$X_i' = ((X_i * a) + (Y_i * b) + (i * c)) mod W$$ $$Y_i' = ((X_i * d) + (Y_i * e) + (i * f)) mod H$$ 然后在q次操作以后,把n个点的坐标输出来。题目保证,总共的变换次数不超过50000次。

【算法】
因为总共变换的次数不超过50000次,所以问题就在于如何快速地选中离$$(x_i, y_i)$$曼哈顿距离小于等于$$E_i$$的点。
显然满足条件的区域是一个旋转了45°的正方形,所以我们只要把坐标旋转45°就好了。也就是这样子:$$x’=x+y, y’=x-y+h$$。
好了,这样子问题就转化成如何快速选中一个所有边都平行于坐标轴的矩形内部点的问题。
显然这题直接用线段树套个set可以做到$$O(\log^2 n)$$ per operation. 但是无情地TLE……
尝试使用KD Tree解决。
显然把点都插入KDTree,然后询问就$$O(\sqrt n)$$的了。
但是有一个问题,选中这些点以后,要将其从KDTree中删除,将坐标变换以后再插入。而KDTree是一个类似二叉搜索树的数据结构,但坑爹的是不能旋转,这样若干次操作以后,KDTree就会退化。
打着想水过的念头写了一下,果断TLE。
一个可行的解决方案是操作了$$\sqrt n$$个结点以后,就rebuild整棵树。但这样整体复杂度就是$$O(n\sqrt n)$$的。
之前在ACM_DIY群问了一下这个问题,数据结构帝CLJ说Scapegoat_tree可以不旋转只rebuild就达到均摊$$\log n$$的复杂度。去膜拜过wiki以后,发现确实可以做到。
于是写了一下,居然就过了。
所谓Scapegoat_tree,就是如果左右子树中的某个size超过了$$\alpha$$*this->size,那么就rebuild这棵子树。虽然看起来很傻X,但是确实可以证明复杂度是lg级别的。当然$$0.5 < \alpha < 1$$。 而所谓KDTree就是在第i层的子树都取其关于第i % K维的中位数的那个结点作为根,然后左右子树递归下去。 不明白的建议看看英文wiki。 【时空分析】 最坏的计算量是$$50000 * \sqrt{50000}$$级别的。 空间复杂度是O(n)的。 【其它】 截个图留念一下,这种现在只有我过掉这题的感觉真是好爽 :Delighted:

【代码】

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
template  void _checkmin(T &t, T x){if (t == -1) t = x; if (x < t) t = x;}
template  void _checkmax(T &t, T x){if (t == -1) t = x; if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
typedef long long lld;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
#define DEBUG(a) cout << #a" = " << (a) << endl;
#define DEBUGARR(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
const int N = 105555;
const int INF = 1000000000;
const double mul = 0.7;
int Tc;
int n, q, w, h;

struct point {
	int x, y, id, rx, ry;
	point() {}
	void trans() {
		rx = x + y;
		ry = x - y + h;
	}
}p[N], tp[N];

int pt, ptr_t;
struct Node {
	int size;
	bool exist, div;
	point mid;
	Node *lc, *rc;
	Node() {size = exist = 0;}

	bool judge() {
		return !size || lc->size > mul * size || rc->size > mul * size;
	}
}pool[N * 5], *root, *null = &pool[0], *ptr[N];

inline bool cmpx(const point &a, const point &b)  { return a.rx < b.rx || (a.rx == b.rx && a.id < b.id); }
inline bool cmpy(const point &a, const point &b)  { return a.ry < b.ry || (a.ry == b.ry && a.id < b.id); }
inline bool cmp(const point &a, const point &b, const bool &div) { return div ? cmpy(a, b) : cmpx(a, b); }

Node *build(point *a, int l, int r, bool div, bool type = 1) {
	if (l > r) return null;
	int mid = (l + r) / 2;
	Node *p = type ? &pool[pt++] : ptr[--ptr_t];
	nth_element(a + l, a + mid,  a + r + 1, div ? cmpy : cmpx);
	p->div = div;
	p->mid = a[mid];
	p->exist = 1;
	p->lc = build(a, l, mid - 1, !div, type);
	p->rc = build(a, mid + 1, r, !div, type);
	p->size = p->lc->size + p->rc->size + 1;
	return p;
}

void dfs(Node *p) {
	if (p == null) return;
	if (p->exist) {
		tp[ptr_t] = p->mid;
		ptr[ptr_t++] = p;
	}
	dfs(p->lc);
	dfs(p->rc);
}

void rebuild(Node *&p) {
	ptr_t = 0;
	dfs(p);
	p = build(tp, 0, ptr_t - 1, p->div, 0);
}


void insert(Node *&p, point a, bool div, bool re = 0) {
	if (p == null) {
		p = &pool[pt++];
		p->div = div;
		p->exist = 1;
		p->size = 1;
		p->mid = a;
		p->lc = p->rc = null;
	} else {
		p->size++;
		bool tag = p->judge();
		if (cmp(a, p->mid, div)) {
			insert(p->lc, a, !div, re | tag);
		} else {
			insert(p->rc, a, !div, re | tag);
		}
		if (!re && tag) rebuild(p);
	}
}

vector  vec;

void getvec(Node *&p, int lx, int ly, int rx, int ry, bool re = 0) {
	if (p->size == 0) return;
	if (p->exist && lx <= p->mid.rx && p->mid.rx <= rx && ly <= p->mid.ry && p->mid.ry <= ry) {
		vec.push_back(p->mid.id);
		p->exist = 0;
		p->size--;
	}
	bool tag = p->judge();
	if (p->div ? ly <= p->mid.ry : lx <= p->mid.rx) getvec(p->lc, lx, ly, rx, ry, re | tag);
	if (p->div ? ry >= p->mid.ry : rx >= p->mid.rx) getvec(p->rc, lx, ly, rx, ry, re | tag);
	p->size = p->lc->size + p->rc->size + p->exist;
	if (!re && tag) rebuild(p);
}

int main() {
	scanf("%d", &Tc);
	for (int ri = 1; ri <= Tc; ri++) {
		pt = 1;
		scanf("%d%d%d%d", &n, &q, &w, &h);
		for (int i = 1; i <= n; i++) {
			scanf("%d%d", &p[i].x, &p[i].y);
			p[i].id = i;
			p[i].trans();
			tp[i] = p[i];
		}
		root = build(tp, 1, n, 0);
		for (int i = 0; i < q; i++) {
			int x, y, E, a, b, c, d, e, f;
			scanf("%d%d%d%d%d%d%d%d%d", &x, &y, &E, &a, &b, &c, &d, &e, &f);
			int lx, ly, rx, ry;
			lx = x + y - E;
			ly = x - y - E + h;
			rx = x + y + E;
			ry = x - y + E + h;
			checkmax(lx, 0);
			checkmax(ly, 0);
			checkmin(rx, w + h);
			checkmin(ry, w + h);
			vec.clear();
			getvec(root, lx, ly, rx, ry);
			foreach (it, vec) {
				lld ix = p[*it].x;
				lld iy = p[*it].y;
				int tx = ((ix * a) + (iy * b) + ((lld)(*it) * c)) % w;
				int ty = ((ix * d) + (iy * e) + ((lld)(*it) * f)) % h;
				p[*it].x = tx;
				p[*it].y = ty;
				p[*it].trans();
				insert(root, p[*it], 0);
			}
		}
		printf("Case #%d:\n", ri);
		for (int i = 1; i <= n; i++) {
			printf("%d %d\n", p[i].x, p[i].y);
		}
	}
}

Codeforces Round #157

传送门
比赛的时候就很慢很慢地搞出前三题……然后rating加了5,囧
记一下自己犯圡的地方好了。
258A
不说了。
258B
一开始看错题了,但是数位dp的部分还是写得很快的。后来发现看错题以后,感觉后面那部分很难算,用dp写了很久(组合计数也太不熟练了),总算pass了。
值得记录的一点是即使是分类相同的项里面取,也应该看成有顺序的,最后再乘6!这样的算法比较科学。
实际上最后那一部分10^7的dfs就可以了。对数据范围不够敏感……作为一个ACMer,能暴力就暴力是基本原则。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
template  void _checkmin(T &t, T x){if (t == -1) t = x; if (x < t) t = x;}
template  void _checkmax(T &t, T x){if (t == -1) t = x; if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
typedef long long lld;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
#define DEBUG(a) cout << #a" = " << (a) << endl;
#define DEBUGARR(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
const int N = 12;
const int Mod = 1000000007;
int n;
int f[N][N][2];
char s[N];

int A6(int x) {
	if (x < 6) return 0;
	long long ret = 1;
	for (int i = 0; i < 6; i++) {
		ret = ret * (x - i);
		ret %= Mod;
	}
	return ret;
}

int Pow(long long a, int b) {
	long long ret = 1;
	while (b) {
		if (b & 1) {
			ret = ret * a;
			ret %= Mod;
		}
		a *= a;
		a %= Mod;
		b >>= 1;
	}
	return ret;
}

int C(int m, int n) {
	if (m < n) return 0;
	long long ret = 1;
	for (int i = 0; i < n; i++) {
		ret = ret * (m - i);
		ret %= Mod;
		ret = ret * Pow(i + 1, Mod - 2);
		ret %= Mod;
	}
	return ret;
}

int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	memset(f, 0, sizeof(f));
	f[0][0][1] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int o = 0; o < 2; o++) {
				for (int k = 0; k <= (o ? s[i + 1] - '0' : 9); k++) {
					int &t = f[i + 1][j + (k == 4 || k == 7)][o && (k == s[i + 1] - '0')];
					t += f[i][j][o];
				}
			}
		}
	}
	f[n][0][0] += Mod - 1;
	f[n][0][0] %= Mod;
	int sum = 0;
	int ans = 0;
	int g[25][25][7];
	memset(g, 0, sizeof(g));
	g[0][0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= 6; k++) {
				g[i + 1][j][k] += g[i][j][k];
				g[i + 1][j][k] %= Mod;
				for (int o = 1; k + o <= 6 && o * i + j <= n && o <= f[n][i][0] + f[n][i][1]; o++) {
					g[i + 1][j + o * i][k + o] += 1LL * g[i][j][k] * C(f[n][i][0] + f[n][i][1], o) % Mod;
					g[i + 1][j + o * i][k + o] %= Mod;
				}
			}
		}
	}
	for (int i = 0; i <= n; i++) {
		ans += 1LL * sum * (f[n][i][0] + f[n][i][1]) % Mod;
		ans %= Mod;
		sum += g[n][i][6] * 720LL % Mod;
//		printf("%d %d\n", i, g[n][i][6]);
		sum %= Mod;
	}
	cout << ans << endl;
}

258C
直接枚举约数然后每个容斥统计。一开始觉得复杂度有点悬,好像是$$O(n\sqrt{n} \log n)$$的,但是突然就想起来[1,n]之间的约数个数应当是$$O(n\log n)$$级别的(参见筛法),所以整个算法应该是$$O(n\sqrt{n} + n \log^2 n)$$的

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
template  void _checkmin(T &t, T x){if (t == -1) t = x; if (x < t) t = x;}
template  void _checkmax(T &t, T x){if (t == -1) t = x; if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
typedef long long lld;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
#define DEBUG(a) cout << #a" = " << (a) << endl;
#define DEBUGARR(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }

const int N = 105555;
const int Mod = 1000000007;
int n;
int a[N];
int sum[N];
int num[N];

int Pow(long long a, int b) {
	long long ret = 1;
	while (b) {
		if (b & 1) ret = ret * a % Mod;
		a = a * a % Mod;
		b >>= 1;
	}
	return ret;
}

int main(){
	scanf("%d", &n);
	set  Set;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		sum[a[i]]++;
	}
	for (int i = 100000; i >= 0; i--) {
		sum[i] = sum[i + 1] + sum[i];
	}
	long long ans = 0;
	for (int i = 1; i <= 100000; i++) {
		if (sum[i]) {
			vector  vec;
			for (int j = 1; j * j <= i; j++) {
				if (i % j == 0) {
					vec.push_back(j);
					if (j * j != i) vec.push_back(i / j);
				}
			}
			num[i] = vec.size() + 1;
			sort(vec.begin(), vec.end());
			long long ret = 1;
			for (int j = (int)(vec.size()) - 2; j >= 0; j--) {
				int now = sum[vec[j]];
				now -= sum[vec[j + 1]];
				ret = ret * Pow(j + 1, now) % Mod;
			}
			long long tmp = Pow(vec.size(), sum[vec[vec.size() - 1]]) - Pow((int)vec.size() - 1, sum[vec[vec.size() - 1]]);
			tmp += Mod;
			tmp %= Mod;
//			cout << i << " " << ret * tmp << endl;
			ans += 1LL * ret * tmp % Mod;
			ans %= Mod;
		}
	}
	cout << ans << endl;
	return 0;
}

258D
这种算数目的数学期望题……
其实就利用概率论与数理统计之前学到的那个将$$E(x)$$分解为若干个$$E(x_i)$$之和,然后分别算期望,叠加起来就好了。
这些随机变量$$x_i$$之间有关无关都是没有关系的。
至于为什么能这么搞,那是因为E(x)本来计算公式就是线性的……

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
template  void _checkmin(T &t, T x){if (t == -1) t = x; if (x < t) t = x;}
template  void _checkmax(T &t, T x){if (t == -1) t = x; if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
typedef long long lld;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
#define DEBUG(a) cout << #a" = " << (a) << endl;
#define DEBUGARR(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
const int N = 1005;
int n, m;
int a[N];
double p[N][N];

int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			p[i][j] = a[i] > a[j];	
		}
	}
	for (int i = 0; i < m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		for (int j = 1; j <= n; j++) {
			if (j != x && j != y) {
				p[j][x] = p[j][y] = (p[j][x] + p[j][y]) / 2;
				p[x][j] = p[y][j] = (p[x][j] + p[y][j]) / 2;
			}
		}
		p[x][y] = p[y][x] = 0.5;
	}
	double ans = 0;
	for (int i = 1; i < n; i++) {
		for (int j = i + 1; j <= n; j++) {
			ans += p[i][j];
		}
	}
	printf("%.12lf\n", ans);
}

258E
对这种不要求在线算法的情况,设计一个合理的计算顺序是至关重要,离线算法相对于在线算法的一个很大的优势就在于计算顺序可以按自己调。
这里也不例外。
首先将子树转化为dfs序中连续一段已经是很old的技巧了,然后按dfs序列从左往右扫,每个询问就只进栈两次再出栈两次。
这样只要用线段树统计出目前被覆盖的点的数目就可以了。这个统计的方法类似于用线段树求矩形并的面积。
具体方法就是记录当前区间的最小值以及这个最小值的数目就可以轻松统计出来了。

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 100005;
int n, m, ot;
int st[N], ed[N];
int order[N];
vector  E[N];

void dfs(int x, int fa) {
	order[++ot] = x;
	st[x] = ot;
	for (vector ::iterator it = E[x].begin(); it != E[x].end(); it++) {
		if (*it != fa) {
			dfs(*it, x);
		}
	}
	ed[x] = ot;
}

	struct Node {
		int l, r, minv, num, d;
		Node *lc, *rc;
		Node(){}
		Node(int l, int r):l(l), r(r) { num = r - l + 1; minv = d = 0; lc = rc = NULL; }
		bool fit(int _l, int _r) { return _l <= l && r <= _r; }
		void pushdown() {
			if (d) {
				minv += d;
				if (lc) {
					lc->d += d;
					rc->d += d;
				}
				d = 0;
			}
		}

		void update() {
			if (lc) {
				minv = min(lc->minv + lc->d, rc->minv + rc->d);
				num = 0;
				if (lc->minv + lc->d == minv) num += lc->num;
				if (rc->minv + rc->d == minv) num += rc->num;
			}
		}
	}tr[N << 2], *root = &tr[1];

	void build(int p, int l, int r) {
		tr[p] = Node(l, r);
		int mid = (l + r) / 2;
		if (l != r) {
			tr[p].lc = &tr[p * 2];
			tr[p].rc = &tr[p * 2 + 1];
			build(p * 2, l, mid);
			build(p * 2 + 1, mid + 1, r);
		}
	}

	void add(Node *p, int l, int r, int x) {
		p->pushdown();
		if (p->fit(l, r)) {
			p->d += x;
		} else {
			int mid = (p->l + p->r) / 2;
			if (l <= mid) add(p->lc, l, r, x);
			if (r >  mid) add(p->rc, l, r, x);
			p->update();
		}
	}

int a[N], b[N];
int ans[N];
vector  in[N], out[N];

int main() {
	scanf("%d%d", &n, &m);
	for (int x, y, i = 1; i < n; i++) {
		scanf("%d%d", &x, &y);
		E[x].push_back(y);
		E[y].push_back(x);
	}
	dfs(1, 0);
	build(1, 1, n);
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &a[i], &b[i]);
		in[st[a[i]]].push_back(i);
		in[st[b[i]]].push_back(i);
		out[ed[a[i]]].push_back(i);
		out[ed[b[i]]].push_back(i);
	}
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		vector ::iterator it;
		for (it = in[i].begin(); it != in[i].end(); it++) {
			add(root, st[a[*it]], ed[a[*it]], 1);
			add(root, st[b[*it]], ed[b[*it]], 1);
			cnt++;
		}
		ans[order[i]] = root->minv + root->d ? n - 1 : n - root->num - !!cnt ;
		for (it = out[i].begin(); it != out[i].end(); it++) {
			add(root, st[a[*it]], ed[a[*it]], -1);
			add(root, st[b[*it]], ed[b[*it]], -1);
			cnt--;
		}
	}
	for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
}

记ACM生涯的第一个First Blood 【2011 Chengdu Site —— Online Contest 】

今天拿了A题的First Blood.

截止3个小时的时候,依然是1个AC,近300个提交

其实开搞这题的时候是很犹豫的。毕竟瞬间n个提交,0AC…于是果断觉得是坑爹题.

YY了一下,得到了个sqrt(n)*Q*t的算法.算了算复杂度非常有压力.

但是想想块状表的常数小到爆了…于是写了个对应复杂度的3重循环试试会不会TLE.结果返回了WA!!!

于是果断开敲,把程序搞了出来.sample调了下..没过= =

然后颓然发现我统计的是他防守住了多少波。点点点点啊.但是块状表本身不是很熟.不想去改动它

于是瞬间上了树状数组(反正就几行)统计每一位被攻击了几次,把那个减一下就是答案了…

接着感觉没啥好改的了,就交了…看着100+个提交…0AC.看着都胆寒啊- -….然后…就返回了AC

以上扯淡,下面说说我的解法。

【题目地址】http://acm.hdu.edu.cn/showproblem.php?pid=4031

【题解】

首先是对n个格子均匀分块。设每个块的大小为L。

那么对于攻击的操作,我们考虑对每个块设定标记使得整个块的操作能够不搞到底层就可以维护起来。需要的时候再把标记传下去。

可以围观到0<=t<=50。可以考虑在上面作文章。

我的标记是由以下几个东西组成的:

1、int l,r表示块的起始和终结位置

2、int Time 表示这个块内的元素最后一次被打到的时间是什么时候。

3、int F[55],pre[55] 我们可以将块内元素按照 (Time-最后一次被打的时间) 分成t+1([0,t])类。如果超过这个减出来的值超过t的,就可以变成t,因为超过t的无论接下来什么时间来了攻击,都可以抵挡,和等于t的其实是一样的…。分成这t+1类以后,F[i]表示第i类元素将会承受住多少次攻击(= =就是这地方我搞错了,就套了个树状数组,其实可以维护成第i类元素将会被打中多少次)。pre[i]表示第i类元素上一次被打的时候是什么时间。

 

这样,在攻击操作来临的时候,我们对于整块的,就去更新一下里面的F[55]和pre[55],对于不是整块的,就直接暴力…

这一步的时间复杂度是O( (n/L)*t + 2*(L+t) )

然后对于询问操作,就简单地把标记推下去,然后统计就好了。

这一步时间复杂度O( L )

如果粗略地令L=sqrt(n)。那么复杂度就是O(Q*t*sqrt(n))。

现在我们尝试在其中寻找到平衡点。

令(n/L)*t = L得L=sqrt(n*t)

于是第一步时间复杂度(n*t/sqrt(n*t) + sqrt(n*t) ) 就是O(sqrt(n*t))

第二部同样是O(sqrt(n*t))

最终复杂度是O(Q*sqrt(n*t))

程序在218…写得也比较搓…就不发了。。。

By edward_mj@Evzones

[codeforces 85D]【平衡树】

【题意】

n个操作

每个操作可以是

add x  把x加进set里

del x   把x从set中删除

sum  令A[1..m]按递增序表示set中的函数。求Sum{A[i] | i%5==3}

【算法】

直接弄棵平衡树。每个结点维护下面几个域。 long long Sum[5] ,offset ,delta,key。

然后标记上下传就可以了,不错的平衡树练手题目。

尝试了一下struct封装好各种操作的Splay。。。感觉还挺舒服,但是写得爆长。。。

我感觉离散化以后线段树也可以搞。

或者直接建5棵平衡树。index变的时候就裂开然后再合并就好了。

【其它】

看了一下watashi飘逸的treap。

然后再看了一下最短的那个人。。。

修改用一个vector二分了个位置(lower_bound),然后直接insert erase。

然后统计直接for (i=3;i

特么坑爹啊!!!!!yandex.algorithm的题这样被人水过啊。

又想起NOI2003文本编辑器pascal那个不能吐槽的move=_=…特么比正解什么的都跑得快…