【BZOJ 4552】[TJOI2016&HEOI2016] 排序

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4552
神犇题解:http://maghsk.github.io/2016/05/05/20160506-bzoj-4552-tjoi2016heoi2016/

解题报告

之前在BC上看到过这道题:http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=680&pid=1004
这就不知道是谁抄谁的了

考虑直接做的话,似乎没法用任何数据结构来维护的样子
于是二分最后的答案 $ p$ ,将小于 $ p$ 的置为0,大于 $ p$ 的搞成1
这样的话,排序操作就变成了区间查询和区间赋值
于是搞一个线段树什么的就可以啦!

【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;
}

【BZOJ 4262】Sum

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4262
神犇题解-1:http://www.cnblogs.com/clrs97/p/4824806.html
神犇题解-2:http://blog.csdn.net/qq_34637390/article/details/51313126

题解

我们不妨将所有询问按照右端点\(r_i\) 排序
假设当前处理的所有询问右端点统一为last
定义\(val_i^{last} = \min (\{ {a_j}|j \in [i,last]\} )\)
定义\(sum_i^{last} = \sum\limits_{j = i}^{last} {val_i^j}\)
不难发现对于左右端点在l-r的所有区间的min和为\(\sum\limits_{i = l}^r {sum_i^r}\)
更进一步,每一个原题中提到的询问可以拆成:\(\sum\limits_{i = {l_1}}^{{r_1}} {sum_i^{{r_2}}} – \sum\limits_{i = {l_1}}^{{r_1}} {sum_i^{{l_2} – 1}}\)

接下来的事情就是用线段树来维护val和sum辣!
考虑last向右移动一个单位,我们首先需要将一些点的val更新
然后我们需要将每一个点当前的val累加到sum里面去

每一个点维护四个变量a,b,c,d来表示标记
定义 new_val = a * val + b * len
定义 new_sum = sum + c * val + d * len
显然更新val需要用到的参数是 {0,val',0,0}
而默认的参数则应该为 {1,0,0,0}
更新sum的参数则应该为 {1,0,1,0}

于是就可以将这两种标记一起下传了
至于为什么可以混在一起?
因为这货是矩阵乘法啊!
ps:矩阵乘法并没有交换律,只有结合律,所以在修改时也得下传标记

Code

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

const int N = 100000+9;
const int M = N << 1;
const int MOD = 1000000000;
const int SEED1 = 1023;
const int SEED2 = 1025;

int n,m,tot,arr[N],stk[N];
LL vout[N];
struct Query{
	int lim,l,r,t,id;
	inline bool operator < (const Query &B) const {
		return lim < B.lim;
	}
}q[M];

namespace Segment_Tree{
	#define SEG Segment_Tree
	int ch[M][2],L,R,cnt,root;
	LL sum[M],val[M],ans_tmp;
	struct Tag{
		LL a,b,c,d;
		inline Tag() {a=1;b=c=d=0;}
		inline Tag(LL a, LL b, LL c, LL d):a(a),b(b),c(c),d(d) {}
		inline Tag operator * (const Tag &B) {
			return (Tag){a*B.a, B.b+b*B.a, a*B.c+c, B.d+d+b*B.c};
		}
	}tag[M],delta;
	
	void Build(int &w, int l, int r) {
		w = ++cnt;
		tag[w] = Tag(1,0,0,0);
		val[w] = sum[w] = 0;
		if (l < r) {
			int mid = l + r + 1 >> 1;
			Build(ch[w][0],l,mid-1);
			Build(ch[w][1],mid,r);
		}
	} 
	
	inline void init() {
		cnt = 0;
		Build(root,1,n);
	}
	
	inline void Add(int w, int l, int r, Tag v) {
		static int len; len = r - l + 1;
		sum[w] += val[w] * v.c + len * v.d;
		val[w] = val[w] * v.a + len * v.b;
		tag[w] = tag[w] * v;
	}
	
	inline void push_down(int w, int l, int mid, int r) {
		Add(ch[w][0],l,mid-1,tag[w]);
		Add(ch[w][1],mid,r,tag[w]);
		tag[w] = Tag(1,0,0,0);
	}
	
	inline void GetSum() {
		Add(root,1,n,Tag(1,0,1,0));
	}
	
	void Modify(int w, int l, int r) {
		if (L <= l && r <= R) {
			Add(w,l,r,delta);
		} else {
			int mid = l + r + 1 >> 1;
			if (tag[w].a != 1 || tag[w].b || tag[w].c || tag[w].d) 
				push_down(w,l,mid,r);
			if (L < mid) Modify(ch[w][0], l, mid-1);
			if (R >= mid) Modify(ch[w][1], mid, r);
			val[w] = val[ch[w][0]] + val[ch[w][1]];
			sum[w] = sum[ch[w][0]] + sum[ch[w][1]];
		}
	}
	
	inline void modify(int l, int r, int v) {
		delta = Tag(0,v,0,0);
		L = l, R = r;
		Modify(root,1,n);
	}
	
	void query(int w, int l, int r) {
		if (L <= l && r <= R) {
			ans_tmp += sum[w];
		} else {
			int mid = l + r + 1 >> 1;
			if (tag[w].a != 1 || tag[w].b || tag[w].c || tag[w].d) 
				push_down(w,l,mid,r);
			if (L < mid) query(ch[w][0], l, mid-1);
			if (R >= mid) query(ch[w][1], mid, r);
		}
	}
	
	inline LL query(int l, int r) {
		ans_tmp = 0;
		L = l; R = r;
		query(root,1,n);
		return ans_tmp;
	}
};

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() {
	m = read();
	for (int i=1,l1,l2,r1,r2;i<=m;i++) {
		l1 = read(); r1 = read();
		l2 = read(); r2 = read();
		if (l2 > 1) q[++tot] = (Query){l2-1,l1,r1,-1,i};	
		q[++tot] = (Query){r2,l1,r1,1,i};
		n = max(n, max(r1, r2));
	}
	sort(q+1, q+1+tot);
	for (int i=1,c1=SEED1,c2=SEED2;i<=n;i++) {
		arr[i] = c1 ^ c2;
		c1 = (LL)SEED1 * c1 % MOD;
		c2 = (LL)SEED2 * c2 % MOD;
	}
	
	SEG::init();
	for (int i=1,top=0,cur=1;i<=n;i++) {
		while (top && arr[stk[top]] > arr[i]) top--;
		SEG::modify(stk[top]+1, i, arr[i]);
		SEG::GetSum(); stk[++top] = i;
		while (cur <= tot && q[cur].lim == i) {
			vout[q[cur].id] -= SEG::query(q[cur].l, q[cur].r) * q[cur].t;
			cur++;
		}
	}
	SEG::init();
	for (int i=1,top=0,cur=1;i<=n;i++) {
		while (top && arr[stk[top]] < arr[i]) top--;
		SEG::modify(stk[top]+1, i, arr[i]);
		SEG::GetSum(); stk[++top] = i;
		while (cur <= tot && q[cur].lim == i) {
			vout[q[cur].id] += SEG::query(q[cur].l, q[cur].r) * q[cur].t;
			cur++;
		}
	}
	
	for (int i=1;i<=m;i++) 
		printf("%lld\n",vout[i]);
	return 0;
}

【BZOJ 4540】[HNOI2016] 序列

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4540
数据生成器:http://paste.ubuntu.com/23631812/
神犇题解-线段树:http://blog.csdn.net/qq_34637390/article/details/51313126
神犇题解-莫队:https://blog.sengxian.com/solutions/bzoj-4540

解题报告

这题好神啊!莫队和线段树的做法都好神啊!

1. 莫队做法

我们只需要考虑如何O(1)进行转移。
因为是转移,所以一端是固定的,不妨设固定的是左端。
现在从左向右考虑右端点,不难发现:最小值不增(如下图所示)

通过观察我们还可以发现:除了第④段,其他几段的长度都是固定的
于是我们先预处理一下相关信息,对于第④段这种进行特殊处理。
因为第④段这货是l~r中的最小值,所以我们搞一个RMQ就可以特殊处理啦!
这样一来,转移就可以做到O(n),于是就可以上O(n^1.5)的莫队辣!

2. 线段树做法

因为此题和BZOJ_4262 一毛一样,所以就不单独写了。
这里有一份很好的题解,强烈推荐:http://blog.csdn.net/qq_34637390/article/details/51313126

Code (莫队version)

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

const int N = 100000+9;
const int INF = 2e9;

struct Query{
	int l,r,blk,num;
	inline bool operator < (const Query &B) const {
		return blk < B.blk || (blk == B.blk && r < B.r);
	}
}q[N];
int n,m,sqr,top,val[N],stk[N],pos[N],lft[N],rit[N];
LL vout[N],sum_right[N],sum_left[N];

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;
}

namespace Sparse_Table{
	#define ST Sparse_Table
	int sur[N*3][20],arr[N*3][20],POW[20],log[N];
	
	inline void init() {
		POW[0] = 1;
		for (int i=1;i<=17;i++) 
			POW[i] = POW[i-1] << 1;
		for (int i=1,w=1;i<=n;w=1,++i) 
			while (w * 2 <= i) w <<= 1, log[i]++;
		
		for (int i=1;i<=n;i++) {
			arr[i][0] = val[i];
			sur[i][0] = i;
		}
		for (int j=1,cur=1;j<=17;j++,cur<<=1) {
			for (int i=1;i<=n;i++) {
				if (arr[i][j-1] < arr[i+cur][j-1]) {
					arr[i][j] = arr[i][j-1];
					sur[i][j] = sur[i][j-1];
				} else {
					arr[i][j] = arr[i+cur][j-1];
					sur[i][j] = sur[i+cur][j-1];
				}
			}
		}
	}
	
	inline int query(int l, int r) {
		int w = log[r-l+1];
		if (arr[l][w] < arr[r-POW[w]+1][w]) return sur[l][w];
		else return sur[r-POW[w]+1][w];
	}
};

inline LL move_right(int l, int r) {
	int p = ST::query(l, r);
	return sum_left[r] - sum_left[p] + (LL)val[p] * (p - l + 1);
}

inline LL move_left(int l, int r) {
	int p = ST::query(l, r); 
	return sum_right[l] - sum_right[p] + (LL)val[p] * (r - p + 1);
}

inline void prework() {
	stk[top = 0] = -INF;
	for (int i=1;i<=n;i++) {
		while (stk[top] > val[i]) top--;
		lft[i] = pos[top];
		sum_left[i] = sum_left[pos[top]] + (LL)(i-pos[top]) * val[i]; 
		stk[++top] = val[i];
		pos[top] = i;
	}
	
	pos[top = 0] = n+1;
	for (int i=n;i;i--) {
		while (stk[top] >= val[i]) top--;
		rit[i] = pos[top];
		sum_right[i] = sum_right[pos[top]] + (LL)(pos[top]-i) * val[i];
		stk[++top] = val[i];
		pos[top] = i;
	}
	
	ST::init();
}

int main(){
	n = read(); m = read();
	sqr = sqrt(n);
	for (int i=1;i<=n;i++)
		val[i] = read();
	prework();
	for (int i=1;i<=m;i++) {
		q[i].num = i;
		q[i].l = read(); 
		q[i].r = read();
		q[i].blk = q[i].l / sqr;
	}
	sort(q+1, q+1+m);
	
	LL cur = val[1];
	for (int k=1,l=1,r=1;k<=m;k++) {
		while (r < q[k].r) cur += move_right(l,r+1), r++;
		while (r > q[k].r) cur -= move_right(l,r), r--;
		while (l < q[k].l) cur -= move_left(l,r), l++;
		while (l > q[k].l) cur += move_left(l-1,r), l--;
		vout[q[k].num] = cur;
	}
	
	for (int i=1;i<=m;i++) 
		printf("%lld\n",vout[i]);
	return 0;
}

ps:这一份代码并不能处理值为负数的情况,至于为什么:我也普吉岛 QwQ

—————————— UPD 2017.2.2 ——————————
这题今天重新想的时候,想到了一个$O(nlog^2n)$的算法
虽然时间复杂度稍高,但思维复杂度和编程复杂度都相对较低

设$l_i$为第i个数离左边第一个比他小的数的距离,$r_i$同理
于是询问整个序列的话,答案就是 $\sum\limits_{i = 1}^n {{a_i} \times {l_i} \times {r_i}} $
然后仍然考虑离线,将询问排序依次做。
对于每一个数,其贡献有三种情况:
1. $l_i$,$r_i$都没有被询问限制
2. 有一个被限制
3. 有两个被限制
于是我们就可以搞一个树套树套树,把这三种情况分别计算即可
复杂度:$O(nlog^3n)$

但我们考虑离线之后,右端点逐渐右移,于是我们搞一个队列什么的维护一下
然后就搞一个树套树维护左端点就好,复杂度$O(nlog^2n)$

【BZOJ 3747】[POI2015] Kinoman

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3747
数据生成器:http://paste.ubuntu.com/15389317/

这题真的是吼啊!来,大家跟我一起喊:“POI赛高!”

考虑固定左端点:
对于每一个元素,第一次出现的位置权值为正
其第二次出现的权值为负,第三次及以后的权值为0
这时不难发现,其实就是求前缀和的最大值
这个O(n)的暴力大家都会

现在来考虑将左端点向右移动1个位置
不难发现是对之前的前缀和数组进行区间加减,并且求最值
这样的话,就可以用线段树来维护辣!

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<set>
#define LL long long
using namespace std;

const int MAXN = 2000000 + 9;

int n,m,t[MAXN/2],w[MAXN/2],aft[MAXN/2],vis[MAXN/2];
LL buf[MAXN/2],vout;

namespace SegmentTree{
	int root, cnt, ls[MAXN], rs[MAXN], ch[MAXN][2];
	LL mx[MAXN], tag[MAXN];
	
	inline void maintain(int w){mx[w] = max(mx[ch[w][0]], mx[ch[w][1]]);}
	inline void pushdown(int w){
		if (!ch[w][0] || !tag[w]) return;
		else {
			for (int i=0; i<2; i++) tag[ch[w][i]] += tag[w], mx[ch[w][i]] += tag[w];		
			tag[w] = 0;
		} 
	}
	
	void build(int &w, int l, int r){
		w = ++cnt; ls[w] = l; rs[w] = r;
		if (l == r) mx[w] = buf[l];
		else {
			int mid = (l + r + 1) / 2;
			build(ch[w][0], l, mid-1);
			build(ch[w][1], mid, r);
			maintain(w);
		}
	}
	
	void modify(int w, int l, int r, int delta){
		if (l <= ls[w] && rs[w] <= r) mx[w] += (LL)delta, tag[w] += delta;
		else {
			pushdown(w);
			int mid = (ls[w] + rs[w] + 1) / 2;
			if (l < mid) modify(ch[w][0], l, r, delta);
			if (mid <= r) modify(ch[w][1], l, r, delta);
			maintain(w);
		}
	}void modify(int l, int r, int delta){modify(root, l, r, delta);} 
	
	LL ans_tmp;
	void query(int w, int l, int r){
		if (l <= ls[w] && rs[w] <= r) ans_tmp = max(ans_tmp, mx[w]);
		else {
			pushdown(w);
			int mid = (ls[w] + rs[w] + 1) / 2;
			if (l < mid) query(ch[w][0], l, r);
			if (r >= mid) query(ch[w][1], l, r);
		}
	} inline LL query(int l, int r) {ans_tmp=0;query(root, l, r);return ans_tmp;}
};

void init(){
	set<int> Q;
	for (int i=1;i<=n;i++){
		buf[i] = buf[i-1];
		if (!Q.count(t[i])) buf[i] += (LL)w[t[i]], Q.insert(t[i]);
		else if (!vis[t[i]]) buf[i] -= (LL)w[t[i]], vis[t[i]] = 1;
	}
}

int main(){
	using namespace SegmentTree;
	cin>>n>>m;
	for (int i=1;i<=n;i++) scanf("%d",&t[i]);
	for (int i=1;i<=m;i++) scanf("%d",&w[i]);
	for (int i=n;i;i--) {if (vis[t[i]]) aft[i] = vis[t[i]]; vis[t[i]] = i;}
	for (int i=1;i<=m;i++) vis[i] = 0;
	init(); build(root, 1, n);
	
	vout = 0;
	for (int i=1;i<=n;i++){
		vout = max(vout, query(i, n));
		modify(i, (aft[i])?aft[i]-1:n, -w[t[i]]);
		if (aft[i]) modify(aft[i], (aft[aft[i]])?aft[aft[i]]-1:n, w[t[i]]);
	} printf("%lld",vout);
	
	return 0;
} 

【Codeforces 712E】Memory and Casinos

题目传送门:http://codeforces.com/problemset/problem/712/E
官方题解:http://codeforces.com/blog/entry/47050

这个题目想一想,还是挺好玩的
推导过程比较复杂,参见这里吧:http://codeforces.com/blog/entry/47050?#comment-314259
话说这次的官方题解真是辣鸡,还不如评论区容易懂…..

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

const int N = 200000+9;

int n,m;
double arr[N];

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;
}

namespace Segment_Tree{
	#define SEG Segment_Tree
	int ch[N][2],cnt,root,T1,L,R;
	double t1[N],t2[N],T2,ans_tmp;
	
	inline void maintain(int w){
		t1[w] = t1[ch[w][0]] * t1[ch[w][1]];
		t2[w] = t2[ch[w][0]] + t2[ch[w][1]] * t1[ch[w][0]];
	}
	
	void Build(int &w, int l, int r) {
		w = ++cnt;
		if (l == r) {
			t1[w] = t2[w] = arr[l];
		} else {
			int mid = l + r + 1 >> 1;
			Build(ch[w][0],l,mid-1);
			Build(ch[w][1],mid,r);
			maintain(w);
		}
	}
	
	void modify(int w, int l, int r) {
		if (l == r) {
			t1[w] = t2[w] = T2;
		} else {
			int mid = l + r + 1 >> 1;
			if (T1 < mid) modify(ch[w][0],l,mid-1);
			else modify(ch[w][1],mid,r);
			maintain(w);
		}
	}
	
	inline void modify(int pos, double nv) {
		T1 = pos; T2 = nv;
		modify(root,1,n);
	}
	
	void query(int w, int l, int r) {
		if (L <= l && r <= R) {
			ans_tmp += t2[w] * T2;
			T2 *= t1[w];
		} else {
			int mid = l + r + 1 >> 1;
			if (L < mid) query(ch[w][0],l,mid-1);
			if (mid <= R) query(ch[w][1],mid,r);
		}
	}
	
	inline double query(int l, int r) {
		ans_tmp = 0; T2 = 1;
		L = l; R = r;
		query(root,1,n);
		return ans_tmp;
	}
};

int main(){
	n = read(); m = read();
	for (int i=1,a,b;i<=n;i++) {
		a = read(); b = read();
		double tmp = (double)a/b;
		arr[i] = (1 - tmp) / tmp;
	}
	SEG::Build(SEG::root,1,n);
	for (int i=1,a,b,c,ty;i<=m;i++) {
		ty = read(); a = read(); b = read();
		if (ty == 1) {
			c = read();
			double tmp = (double)b/c;
			SEG::modify(a,(1-tmp)/tmp);
		} else {
			double tmp = SEG::query(a,b);
			tmp = min(1e20,tmp);
			printf("%.10lf\n",1/(1+tmp));
		}
	}
	return 0;
}

【Codeforces 718C】Sasha and Array

题目传送门:http://codeforces.com/contest/718/problem/C
数据生成器:http://paste.ubuntu.com/23296960/
官方题解:http://codeforces.com/blog/entry/47314

斐波那契数列的话,转移可以用快速幂
于是用线段树来维护转移矩阵就可以辣!

值得一提的是:我之前一直以为斐波那契数列的通项公式没有用
然而鏼爷讲了二次剩余之后,发现其实拿货是可以出成题目考的QAQ

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

const int N = 200000+9;
const int MOD = 1000000007;

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 n,m,arr[N];
struct Matrix{
	int a[3][3];
	inline Matrix() {}
	inline Matrix(int w) {
		memset(a,0,sizeof(a));
		a[1][1] = a[2][2] = w;
	}
	inline Matrix(const Matrix &B) {
		memcpy(this,&B,sizeof(B));
	}
	inline Matrix operator * (const Matrix &B) {
		Matrix ret(0);
		for (int i=1;i<=2;i++) {
			for (int j=1;j<=2;j++) {
				for (int k=1;k<=2;k++) {
					ret.a[i][j] += (LL)a[k][j] * B.a[i][k] % MOD;
					ret.a[i][j] %= MOD;
				}
			}
		}
		return ret;
	}
	inline Matrix operator ^ (LL t) {
		Matrix ret(1),w(*this);
		while (t) {
			if (t & 1) ret = ret * w;
			w = w * w; t >>= 1;
		}
		return ret;
	}
}trans,cur_trans,ori(1);

namespace Segment_Tree{
	#define SEG Segment_Tree
	int ch[N][2],cnt,root,L,R,ans_tmp;
	Matrix mat[N],tag[N];
	
	inline void maintain(int w){
		for (int i=1;i<=2;i++) {
			for (int j=1;j<=2;j++) {
				mat[w].a[i][j] = mat[ch[w][0]].a[i][j] + mat[ch[w][1]].a[i][j];
				mat[w].a[i][j] %= MOD;
			}
		}
	}
	
	inline void push_down(int w) {
		for (int i=0;i<2;i++) {
			tag[ch[w][i]] = tag[ch[w][i]] * tag[w];
			mat[ch[w][i]] = mat[ch[w][i]] * tag[w];
		}
		tag[w] = Matrix(1);
	}
	 
	void Build(int &w, int l, int r) {
		w = ++cnt;
		tag[w] = Matrix(1);
		if (l == r) {
			mat[w].a[1][1] = mat[w].a[2][1] = 1;
			mat[w] = mat[w] * (trans^(arr[l]-1));
		} else {
			int mid = l + r + 1 >> 1;
			Build(ch[w][0],l,mid-1);
			Build(ch[w][1],mid,r);
			maintain(w);
		}  
	}
	
	void Modify(int w, int l, int r) {
		if (L <= l && r <= R) {
			tag[w] = tag[w] * cur_trans;
			mat[w] = mat[w] * cur_trans;
		} else {
			push_down(w);
			int mid = l + r + 1 >> 1;
			if (L < mid) Modify(ch[w][0],l,mid-1);
			if (mid <= R) Modify(ch[w][1],mid,r);
			maintain(w);
		}
	}
	
	inline void modify(int l, int r, int delta) {
		L = l; R = r; 
		cur_trans = trans ^ delta;
		Modify(root,1,n);
	}
	
	void query(int w, int l, int r) {
		if (L <= l && r <= R) {
			ans_tmp += mat[w].a[1][1];
			ans_tmp %= MOD;
		} else {
			push_down(w); 
			int mid = l + r + 1 >> 1;
			if (L < mid) query(ch[w][0],l,mid-1);
			if (mid <= R) query(ch[w][1],mid,r);
			maintain(w); 
		}
	}
	
	inline int query(int l, int r){
		L = l; R = r; ans_tmp = 0;
		query(root,1,n);
		return ans_tmp;
	}
};

int main(){
	n = read(); m = read(); 
	for (int i=1;i<=n;i++) {
		arr[i] = read();
	}
	trans.a[1][2] = trans.a[2][1] = trans.a[2][2] = 1;
	SEG::Build(SEG::root,1,n);
	for (int i=1,ty,a,b,c;i<=m;i++) {
		ty = read(); a = read(); b = read();
		if (ty == 1) {
			SEG::modify(a,b,read());
		} else {
			printf("%d\n",SEG::query(a,b));
		}
	}
	return 0;
}

【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;
}

【UOJ 213】[UNR #1] 争夺圣杯

题目传送门:http://uoj.ac/problem/213
原厂题解:http://c_sunshine.blog.uoj.ac/blog/1860

我发现这道题目,我写了30分的暴力,60分的乱搞,100分的乱搞QAQ

说一说100分的乱搞O(nlogn):
考虑每一个区间的右端点右移一格,左端点不动
那么区间mx要么变成最右边那个,要么不动
考虑计算最右边那货对于答案的贡献,实际上就是区间加减
于是线段树维护一下

其实搞到这里,O(n)的做法就很明显了
因为线段树那里,只需要区间加减,不需要支持中途询问
于是搞一个差分就可以把线段树给去掉

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

const int MAXN = 1000000+9;
const int MOD = 998244353;

int n,arr[MAXN],vout,que[MAXN],lft[MAXN],MX[MAXN],BUF[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;
}

inline void prework(){
	int tot = 0;
	for  (int i=1;i<=n;i++) {
		while (tot && arr[que[tot]] < arr[i]) tot--;
		BUF[1] = (BUF[1]+arr[i])%MOD;
		BUF[i-que[tot]+1] = ((BUF[i-que[tot]+1] - arr[i]) % MOD + MOD ) %MOD;
		lft[i] = i-que[tot]; que[++tot] = i; 
	} tot = 0; que[0] = n+1;
	for (int i=n;i;i--) {
		while (tot && arr[que[tot]] <= arr[i]) tot--;
		if(tot) {
			BUF[que[tot]-i+1] = ((BUF[que[tot]-i+1]-arr[i]) % MOD + MOD) % MOD; 
			BUF[que[tot]-i+lft[i]+1] = (BUF[que[tot]-i+lft[i]+1] + arr[i]) % MOD;
		} que[++tot] = i;
	}
	for (int i=n;i;i--) MX[i] = max(MX[i+1], arr[i]);
}

inline void solve(){
	int tmp = 0, delta = 0;
	for (int i=1;i<=n;i++) {
		delta = ((delta + BUF[i]) % MOD + MOD) % MOD;
		tmp = ((tmp + delta) % MOD + MOD) % MOD;
		vout ^= tmp;
		tmp -= MX[n-i+1];
	}
}

int main(){
	n = read();
	for (int i=1;i<=n;i++) arr[i] = read();
	prework(); solve();
	printf("%d\n",vout);
	return 0;
}

【NOI五连测】[D2T2] 取名字

题目传送门:http://pan.baidu.com/s/1hsLh92W
OJ传送门:http://oi.cdshishi.net:8080/Problem/1713

这一道题目,考试的时候,想了一个小时,完全没有思路,最后搞了30分的暴力QAQ
考试的时候一直在想如何将更改操作应用于硬币上
然而std是用硬币去操作中查询
为什么考试的时候没有想到呢?考试的时候是想到这样反向来搞的,但因为精神不好+懒所以没有深入思考
所以该睡的觉还是要睡的,该开的黑还是要开的

来说一说std的做法:
设一个硬币,比较大的值为mx,较小的值为mn。操作的阈值为v
则操作可以分为3类
1.mn < v
2.mn <= v < mx
3.mx <= v
对于第一类,明显不影响
对于第二类,明显是不管之前状态如何,全部变为mx
对于第三类,就是直接反转
所以我们可以找到最后一个第二类操作,然后查找之后有多少个三类操作即可

至于代码实现方面,我后来写的是BIT+线段树
std是二维线段树
我的要快一点,std空间要少很多,所以还是把std贴出来吧(std建树的时候有一点奇技淫巧)
std:http://paste.ubuntu.com/19496714/
my code:

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define LL long long
using namespace std;

const int MAXN = 100000+9;

int n,m,arr[MAXN],rev[MAXN],val[MAXN],hash[MAXN*3],tot,MX;
vector<int> G[MAXN]; LL vout;

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;
} 

namespace Chair_Tree{
	#define CT Chair_Tree
	#define lowbit(x) ((x)&-(x))
	#define N 10000000
	int cnt,ch[N][2],sum[N],ans_tmp;
	int q1[MAXN],q2[MAXN],root[MAXN*3];
	
	void modify(int &w, int l, int r, int val, int del){
		if (!w) w = ++cnt; sum[w] += del; 
		if (l < r) {
			int mid = (l + r + 1) / 2;
			if (val < mid) modify(ch[w][0],l,mid-1,val,del);
			else modify(ch[w][1],mid,r,val,del);
		}
	}
	
	inline void modify(int pos, int val, int del){
		for (int i=val;i<=tot;i+=lowbit(i)) 
			modify(root[i],1,m,pos,del);
	}
	
	void query(int w, int l, int r, int lim, int rim){
		if (lim <= l && r <= rim) ans_tmp += sum[w];
		else {
			int mid = (l + r + 1) / 2;
			if (lim < mid) query(ch[w][0],l,mid-1,lim,rim); if (rim >= mid) query(ch[w][1],mid,r,lim,rim); 
		}
	}
	
	inline int query(int pos, int l, int r){
		ans_tmp = 0; 
		for (int i=pos;i;i-=lowbit(i)) 
			query(root[i],1,m,l,r);
		return ans_tmp;
	}
	
	inline int GetMX(int L, int R) {
		int t1=0,t2=0,l=1,r=m,mid,tmp=0;
		for (int i=R;i;i-=lowbit(i)) q1[++t1] = root[i];
		for (int i=L;i;i-=lowbit(i)) q2[++t2] = root[i];
		for (int i=1;i<=t1;i++) tmp += sum[q1[i]];
		for (int i=1;i<=t2;i++) tmp -= sum[q2[i]];
		if (!tmp) return 0;
		else while (l < r) {
			mid = (l + r + 1) / 2; tmp = 0;
			for (int i=1;i<=t1;i++) tmp += sum[ch[q1[i]][1]];
			for (int i=1;i<=t2;i++) tmp -= sum[ch[q2[i]][1]]; if (tmp > 0) {
				l = mid;
				for (int i=1;i<=t1;i++) q1[i] = ch[q1[i]][1];
				for (int i=1;i<=t2;i++) q2[i] = ch[q2[i]][1];
			} else {
				r = mid - 1;
				for (int i=1;i<=t1;i++) q1[i] = ch[q1[i]][0];
				for (int i=1;i<=t2;i++) q2[i] = ch[q2[i]][0];
			}
		} return l;
	}
};

inline int find(int w){
	int l=1,r=tot,mid;
	while (l <= r) {
		mid = (l + r) / 2;
		if (hash[mid] < w) l = mid+1; else if (hash[mid] > w) r = mid-1;
		else return mid;;
	}
}

int main(){
	freopen("name.in","r",stdin);
	freopen("name.out","w",stdout); 
	n = read();
	for (int i=1;i<=n;i++) arr[i] = hash[++tot] = read();
	for (int i=1;i<=n;i++) rev[i] = hash[++tot] = read();
	m = read();
	for (int i=1,a,b,c;i<=m;i++) 
		a = read(), b = read(), val[i] = hash[++tot] = read(),
		G[a].push_back(i), G[b+1].push_back(-i);
	sort(hash+1,hash+1+tot);
	tot = unique(hash+1,hash+tot+1)-hash-1;
	for (int i=1;i<=n;i++) arr[i] = find(arr[i]);
	for (int i=1;i<=n;i++) rev[i] = find(rev[i]);
	for (int i=1;i<=m;i++) val[i] = find(val[i]);
	
	for (int k=1;k<=n;k++) {
		for (int i=0;i<(int)G[k].size();i++) { if (G[k][i] > 0) CT::modify(G[k][i],val[G[k][i]],1);
			else CT::modify(-G[k][i],val[-G[k][i]],-1);
		}
		int l=1,r=m,ans=0,mn=min(arr[k],rev[k]),mx=max(arr[k],rev[k]);
		ans = CT::GetMX(mn-1,mx-1);
		if (ans) {
			int tmp = CT::query(tot,ans,m) - CT::query(mx-1,ans,m);
			if (tmp % 2) vout += (LL)hash[mn];
			else vout += (LL)hash[mx];
		} else {
			int tmp = CT::query(tot,0,m) - CT::query(mx-1,0,m);
			if (tmp % 2) vout += (LL)hash[rev[k]];
			else vout += (LL)hash[arr[k]];
		}
	}
	printf("%lld\n",vout);
	return 0;
}	
 

【NOI六连测】[D1T1] 比赛

题目传送门:http://pan.baidu.com/s/1kVjNeeV
离线版题目:http://paste.ubuntu.com/18236489/
数据传送门:http://pan.baidu.com/s/1kUR6kTL

哎呀,绍兴一中的NOIP模拟题,第一眼拿到都一脸懵逼QAQ
想了一会儿发现,不就是总方案数减掉一个三位偏序吗?这个我会!
于是开开心心写完BIT+动态建点的线段树。然后小数据对拍,欸!居然没错 (~ ̄▽ ̄)→))* ̄▽ ̄*)o
然后一跑大数据,哎呀,空间简直炸的飞起! 然后再接下来的一个半小时里一直想办法压空间。
什么unsign short配合char之类的都用上了,然而还是不行QAQ,再加上时间复杂度也不一定过得去,于是弃疗

测完程序,发现CDQ+归并就可以卡过QAQ,然而不会CDQ,于是下午学了一学,还是比较好学的。
然而这还不是高潮!高潮在:这货可以降到一维,然后O(nlogn)轻松过 QAQ
对于任意一个符合条件的(x,y)只会有一种情况(在把A,B,C看成一样的情况下):

A[x] < A[y] 
B[x] > B[y]
C[x] > C[y]

然后不难发现,如果我们把[A,B]&[A,C]拿出来统计一次逆序对的话,这货相当于每一个符合要求的(x,y)被算了2次
于是,跑三遍一维逆序对就好了QAQ 这个能算简单的容斥吗?

BIT + 线段树:http://paste.ubuntu.com/18236197/
CDQ分治:http://paste.ubuntu.com/18236240/
逆序对虐场代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;

const int MAXN = 200000+9;

int n,a[MAXN],b[MAXN],c[MAXN],ord[MAXN];
LL vout;

namespace Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define low(x) (x&(-x))
	int arr[MAXN],sum;
	
	inline void init(){
		memset(arr,0,sizeof(arr));
		sum = 0;}
	
	inline void modify(int pos){
		for (int i=pos;i<=n;i+=low(i))
			arr[i] += 1; sum++;
	} 
	
	inline int query(int pos){
		int ret = 0;
		for (int i=pos;i;i-=low(i))
			ret += arr[i];
		return sum-ret;
	}
};

inline void itv(int *A, int *B){
	BIT::init();
	for (int i=1;i<=n;i++) ord[A[i]] = i;
	for (int j=1,i=ord[j];j<=n;i=ord[++j])
		vout += BIT::query(B[i]),
		BIT::modify(B[i]);
}

int main(){
	freopen("contest.in","r",stdin);
	freopen("contest.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
	itv(a,b); itv(b,c); itv(a,c); 
	printf("%lld\n",vout/2LL);
	return 0;
}

另外,这题做的时候,发现对于小的结构体,貌似直接排序比排指针还要快一点QAQ
可能是因为后期指针寻址也要花时间吧!所以以后CDQ就直接结构体写了吧! 有图有真相:
struct_iterator