【Codeforces 781E】Andryusha and Nervous Barriers

相关链接

题目传送门:http://codeforces.com/contest/781/problem/E
代码参考:http://codeforces.com/contest/781/submission/25269119

解题报告

这题我们先考虑没有墙会害怕的版本
这样的话,我们想象一下是墙冲向一排点
于是搞一个线段树支持区间赋值,区间查询就可以了!

现在考虑加上害怕的限制
那我们可以用二维线段树!
但好难写QwQ ←这货写到一半就弃坑了

于是就去看别人的代码
然后看到了毛爷爷的代码 (毛爷爷这场暴跌 默哀 _(:з」∠)_
然后发现这题又可以暴力………

我们考虑将每一次分开的点打成一包
算上最开始的,不难发现总共只有$O(w+2n)$个包
那每一个包我们插到线段树中,此时总包数是$O((w+2n) \log (w+2n))$的
那么每一次查询我们就暴力每一个节点,于是均摊的复杂度仍然是$O(\log n)$的
代码好写还跑得飞快!

这种有一点暴力思想的数据结构题,我还真的是一点想不出来啊!
比如BZOJ 4712,真的是一点都没往那边想啊!
我一定要在科技树上点亮这个技能!

Code

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

const int N = 5000000;
const int M = 200009;
const int MOD = 1000000007;

int hit,wid,n,cnt;
struct Pack{int h,sum,del;}p[N];
struct Wall{int h,l,r,s;}wall[M];

class Segment_Tree{
	int ans_tmp,tot,root,ch[M][2];
	stack<int> s[M];
	public:
		inline void insert(int p, int id) {
			insert(root, 1, wid, p, id);
		}
		inline int query(int h, int l, int r) {
			ans_tmp = 0; 
			query(root, 1, wid, l, r, h);
			return ans_tmp;
		}
	private:
		void insert(int &w, int l, int r, int p, int v) {
			if (!w) w = ++tot; s[w].push(v);
			if (l < r) {
				int mid = l + r + 1 >> 1;
				if (p < mid) insert(ch[w][0], l, mid-1, p, v);
				else insert(ch[w][1], mid, r, p, v);
			}
		}
		void query(int w, int l, int r, int L, int R, int h) {
			if (L <= l && r <= R) {
				while (!s[w].empty() && p[s[w].top()].h <= h) {
					if (!p[s[w].top()].del) {
						p[s[w].top()].del = 1;
						(ans_tmp += p[s[w].top()].sum) %= MOD;	
					} s[w].pop();
				}
			} else {
				int mid = l + r + 1 >> 1;
				if (L < mid) query(ch[w][0], l, mid-1, L, R, h);
				if (mid <= R) query(ch[w][1], mid, r, L, R, h);
			}
		}
}SGT;

inline int read() {
	char c=getchar(); int ret=0,f=1;
	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;
}

int main() {
	hit = read(); wid = read(); n = read();
	for (int i=1;i<=n;i++) {
		wall[i].h = read();
		wall[i].l = read();
		wall[i].r = read();
		wall[i].s = read();
	}
	for (int i=1;i<=wid;i++) {
		p[++cnt].h = hit + 1;
		p[cnt].sum = 1;
		SGT.insert(i, cnt); 
	} 
	sort(wall+1, wall+1+n, [](const Wall &A, const Wall &B){return A.h > B.h;});
	for (int i=1,h_mx,tmp;i<=n;i++) { 
		tmp = SGT.query(wall[i].h + wall[i].s, wall[i].l, wall[i].r);
		p[++cnt].sum = tmp; p[cnt].h = wall[i].h;
		p[++cnt].sum = tmp; p[cnt].h = wall[i].h;
		if (wall[i].l == 1) SGT.insert(wall[i].r+1, cnt-1);
		else SGT.insert(wall[i].l-1, cnt-1);
		if (wall[i].r == wid) SGT.insert(wall[i].l-1, cnt);
		else SGT.insert(wall[i].r+1, cnt);
	}
	int vout = 0;
	for (int i=1;i<=cnt;i++) 
		(vout += (p[i].del ^ 1) * p[i].sum) %= MOD;
	printf("%d\n",vout);
	return 0;
}

【BZOJ 2877】[NOI2012] 魔幻棋盘

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2877
神犇题解Ⅰ:http://www.cnblogs.com/Randolph87/p/3795729.html
神犇题解Ⅱ:https://blog.sengxian.com/solutions/bzoj-2877

解题报告

首先这货需要有一个结论: $\gcd ({a_1},{a_2}, \cdots ,{a_n}) = \gcd ({a_i}, {a_1} – {a_2},{a_2} – {a_3}, \cdots ,{a_{n – 1}} – {a_n})$
证明的话,想一想辗转相除法就可以啦!
酱紫的话,一维情况我们维护一个差分就可以啦!

现在考虑二维的情况,每一维直接用线段树肯定是不可取的
于是我们考虑答案的表达式: $\gcd (gcd({a_{i,j}},{a_{l,j}} – {a_{l + 1,j}}, \cdots ,{a_{r – 1,j}} – {a_{r,j}}), \cdots ,gcd({a_{i,k}},{a_{l,k}} – {a_{l + 1,k}}, \cdots ,{a_{r – 1,k}} – {a_{r,k}}))$
将每一个 $gcd()$ 的第一项全部提出来,就是 ${\rm{gcd}}({a_{l,j}}, \cdots ,{a_{l,k}})$
这个只有一维,可以用上文提到的情况来解决
剩下的部分每一次修改还是会改到 $O(n)$ 个点
这样是不优雅的,于是考虑在第二维也差分一次的话
那么每一次需要修改的点就只有4个了
于是就可以用二维线段树维护啦!

【UOJ 218】[UNR #1] 火车管理

题目传送门:http://uoj.ac/problem/218
数据生成器:http://paste.ubuntu.com/20456908/

这一道题目,考试的时候,还是想要A掉来着,结果wa得只剩10分QAQ
™我的自定义测试,那么大的数据都没有wa

考试的时候,我的做法是:
单独一棵线段树用来处理询问
然后再用一个二维线段树来维护堆栈
第一维是时间,用来二分最近最近的有效操作
第二维是车站,用来支持二分的查询动作
时间复杂度:O(nlog^2(n))

std的做法是:
任然单独搞一棵线段树来对付询问
对于操作,直接上函数式线段树QAQ
时间复杂度:O(nlogn)

至今都觉得还是我的做法最自然
但他们都说函数式线段树最自然QAQ

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 500000+9;

int n,m,ty,last_ans,arr[MAXN];

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

namespace Segment_Tree{
	#define SEG Segment_Tree
	const int N = MAXN*4;
	int tag[N],sum[N],tm[N],ans_tmp,L,R,DEL;
	
	inline void push_down(int w, int l, int r, int mid){
		tag[w*2] = tag[w*2+1] = tag[w];
		sum[w*2] = (mid-l)*arr[tag[w]];
		sum[w*2+1] = (r-mid+1)*arr[tag[w]];
		tag[w] = 0;
	}
	
	void query(int w, int l, int r){
		if (L <= l && r <= R) ans_tmp += sum[w];
		else {
			int mid = (l + r + 1) / 2;
			if (tag[w]) push_down(w,l,r,mid);
			if (L < mid) query(w*2,l,mid-1);
			if (R >= mid) query(w*2+1,mid,r);
		}
	}inline int query(int l, int r){ans_tmp=0;L=l,R=r;query(1,1,n);return ans_tmp;}
	
	void Modify(int w, int l, int r){
		if (L <= l && r <= R) tag[w] = DEL, sum[w] = (r-l+1)*arr[DEL];
		else {
			int mid = (l + r + 1) / 2;
			if (tag[w]) push_down(w,l,r,mid);
			if (L < mid) Modify(w*2,l,mid-1);
			if (R >= mid) Modify(w*2+1,mid,r);
			sum[w] = sum[w*2] + sum[w*2+1];
		}
	}inline void modify(int l, int r, int del){L=l,R=r,DEL=del;Modify(1,1,n);}
	
	inline int index(int pos){
		int w = 1, l = 1, r = n, mid;
		while (l < r) {
			if (tag[w]) return tag[w];
			else {
				mid = (l + r + 1) / 2;
				if (pos < mid) w = w*2, r = mid-1;
				else w = w*2+1, l = mid;
			}
		}
		return tag[w];
	}
}; 

namespace Persistent_Segment_Tree{
	#define PST Persistent_Segment_Tree
	const int N = 20000000;
	int tag[N],root[N],ch[N][2],tot,cnt,L,R,DEL;
	
	inline int query(int tm, int pos) {
		if (tm < 1) return 0;
		else {
			int w = root[tm], l=1, r=n, mid;
			while (l < r) {
				if (tag[w]) return tag[w];
				else {
					mid = (l + r + 1) / 2;
					if (pos < mid) w = ch[w][0], r = mid-1;
					else w = ch[w][1], l = mid;
				}
			}
			return tag[w];
		}
	}
	
	inline void push_down(int w){
		for (int i=0;i<=1;i++) if (!ch[w][i]) ch[w][i] = ++cnt;
		for (int i=0;i<=1;i++) tag[ch[w][i]] = tag[w];
		tag[w] = 0;
	}
	
	void Modify(int pre, int &w, int l, int r, int tg){
		w = ++cnt; ch[w][1] = ch[pre][1]; 
		ch[w][0] = ch[pre][0]; tag[w] = tg?tg:tag[pre];
		if (L <= l && r <= R) tag[w] = DEL;
		else {
			int mid = (l + r + 1) / 2; 
			if (L < mid) Modify(ch[pre][0],ch[w][0],l,mid-1,tag[w]);
			else if (tag[w]) ch[w][0] = ++cnt, tag[cnt] = tag[w];
			if (mid <= R) Modify(ch[pre][1],ch[w][1],mid,r,tag[w]);
			else if (tag[w]) ch[w][1] = ++cnt, tag[cnt] = tag[w];
			tag[w] = 0;
		}
	}
	
	inline int modify(int l, int r, int val, bool type){
		L = l, R = r, DEL = val; 
		Modify(root[tot], root[(tot+type)], 1, n, 0);
		tot += type; return tot;
	}
};

int main(){
	scanf("%d%d%d",&n,&m,&ty);
	for (int i=1,type,l,r,del;i<=m;i++){
		scanf("%d",&type);
		if (type == 1) {
			l = read(); r = read();
			if (l > r) swap(l, r);
			printf("%d\n",last_ans=SEG::query(l,r));
		} else if (type == 2) {
			l = read();
			int tmp = SEG::index(l);
			int nv = PST::query(tmp-1,l);
			PST::modify(l,l,nv,0);
			SEG::modify(l,l,nv);
		} else {
			l = read(); r = read(); scanf("%d",&del);
			if (l > r) swap(l, r); 
			int tmp = PST::modify(l,r,PST::tot+1,1);
			arr[tmp] = del;
			SEG::modify(l, r, tmp);
		}
	}
	return 0;
}