【BZOJ 3514】Codechef MARCH14 GERALD07加强版

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3514
神犇题解:http://www.cnblogs.com/zhonghaoxi/p/3651591.html

解题报告

这是LCT的经典应用,我们把每条边的权值设为它的编号
然后用LCT动态维护最大生成树
同时记录第$i$条边加入时取代的那一条边的编号$a_i$

对于询问,我们发现对于询问$[l,r]$
只有$a_i < l$的边才会使连通块的大小减少$1$
于是问题变为询问一个区间内小于某个数的个数
这是又是函数式线段树的经典应用

于是这题用LCT和函数式线段树就可以解决
时间复杂度:$O(n \log n)$

相关拓展

这题还可以很方便地将问题改为删掉$[l,r]$的边之后连通块的个数
这个我们将序列倍长,然后直接转化为原问题

【BZOJ 4538】[HNOI2016] 网络

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4538
神犇题解:http://krydom.com/bzoj4538/

解题报告

这题我先说一种怪怪的做法 QwQ
考虑使用主席树,第一维是权值(用BIT搞成后缀和),第二维是DFS序
这样的话,对于询问我们可以在第一维的权值上进行二分
对于每一次二分 $ a$ ,我们可以通过判断覆盖该点的区间个数是否等于所有不小于 $ a$ 的区间个数是否相等

这样话,原问题转化为:在主席树上的区间加减问题
这一块的时空复杂度是 $ O(n{\log ^3}n)$ 的
然后考虑上二分的 $ log$ 这样的话,复杂度就是 $ O(n{\log ^4}n)$ 的
这种做法是自己YY的,感觉很有道理的样子
然而懒得写代码了,也不知道对不对

另外的话,再说一说正解吧!
考虑一条路径,说白了就是查询路径上的点的时候不查到该路径
查询非该路径上的点的时候查询到该路径
这时考虑树链剖分的话,该路径对应的 $ {log(n)}$ 个区间应该忽略,其他部分添加上这个路径的信息
因为是一整块区间抠掉 $ {log(n)}$ 个区间,所以剩余部分也只会有 $ {log(n)}$ 个区间
于是树链剖分暴力搞一搞就可以辣!
时空复杂度比之前的做法应该要稍微优越一点

【CodeChef BTREE】Union on Tree

相关链接

题目传送门:https://www.codechef.com/problems/BTREE
数据生成器:http://paste.ubuntu.com/23671176/
中文题面:http://www.codechef.com/download/translated/OCT14/mandarin/BTREE.pdf
官方题解:https://discuss.codechef.com/questions/53273/btree-editorial
神犇题解Ⅰ:http://xllend3.is-programmer.com/posts/64760.html
神犇题解Ⅱ:https://stalker-blog.apphb.com/post/divide-and-conquer-on-trees-based-on-vertexes

WJMZBMR Orz

又是 青年计算机科学家陈立杰 出的神题!
真的是跪烂!_(:з」∠)_

解题报告

看一看数据范围就可以知道这题复杂度一定只跟 ∑士兵数 相关
于是考虑先把虚树建出来,那么剩下的问题就是在利用虚树的边来统计答案了

1)函数式线段树的做法

考虑k=1,这样的话不用处理重复的问题,于是直接点分治就可以做
但现在有很多的点,于是我们可以将树剖成很多块,每块中恰好又一个城市a有卫兵
更进一步,我们规定这个联通块中任意一个点i到a的距离不大于到其他任意有卫兵的城市的距离
于是我们如果能在每一个联通块中单独处理每一个卫兵的话,就可以不用考虑去重的问题了

我们再仔细观察一下建出来的虚树,发现每一个块就是虚树上的一部分
对于a所在联通块深度最小的那个点,统计一下、加到答案里去
对于a所在联通块的其余边缘节点,再统计一下、从答案中减去

于是剩下的就是如何具体如何统计一条边对于答案的贡献了
我们分两种情况考虑:

  1. v不是u在虚树中的祖先,统计v的子树中、到u的距离为d的点的个数
    这个的话,直接用函数式线段树查就好
  2. v是u的父亲,其余条件相同
    这样的话,似乎与v的距离就不固定了(lca在u ~ v中移动)
    于是先用点分治做出所有点到u的距离为d的点的个数n1
    然后需要减掉v子树外的部分,这样的话,发现到v的距离就固定了
    于是减掉所有点到v的距离为d-dis(u,v)的点数n2
    再加上v子树中到v距离为d-dis(u,v)的点数n3就可以辣!

2)直接用点分治的做法

先用把点分树搞出来,这样就可以O(log^2(n))的时间复杂度内求dis(w,d)
其中dis(w,d)的定义为 到点w距离在d以内的点有多少 (不会的同学可以先去做BZOJ_3730

再考虑把虚树建出来,这样的话唯一的问题就是如何去重了
考虑如果虚树上一条边的两个点的管辖范围没有交集,那么就肯定没有重复
如果有交集,那么设交集的重点为m,交集半径为r'那么直接减掉dis(m,r')就可以辣!

另外还需要预先将完全包含的管辖区间给修改成“相切”的情况,这样才能保证去重完整
还有的话,中点可能落在边上,于是可以在每边的中点加一个点

这样的做法是不是比主席树的做法清真了很多?
然而我还是写了5k+ _ (:з」∠) _
而且如果边带权的话,这题就很难这样做了

Code

最近为什么写啥常数都大到不行啊 QwQ
又是垫底…..

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

const int N = 100000 + 9;
const int M = N << 1;
const int INF = 1e8;

int n,m,T,head[N],to[M],nxt[M],num[N],cost[N];
int anc[N][18],dep[N],val[N],p[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;
}
		
inline void Add_Edge(int u, int v) {
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

void DFS(int w, int f) {
	static int cnt = 0;
	dep[w] = dep[f] + 1;
	anc[w][0] = f; num[w] = ++cnt;
	for (int i=head[w];i;i=nxt[i]) {
		if (!dep[to[i]]) {
			DFS(to[i], w);
		}
	}
}

inline int LCA(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i=17;~i;i--) 
		if (dep[anc[x][i]] >= dep[y]) 
			x = anc[x][i];
	if (x == y) return x;
	for (int i=17;~i;i--) {
		if (anc[x][i] != anc[y][i]) {
			x = anc[x][i];
			y = anc[y][i];
		}
	} 
	return anc[x][0];
}

inline int dis(int x, int y) {
	int lca = LCA(x, y);
	return dep[x] + dep[y] - dep[lca] * 2;
}

class Point_Based_Divide_and_Conquer{
	int fa[N][18],tot[N],sum[N];
	int ans_tmp,root,block_size;
	vector<int> q[N],mul[N];
	bool vis[N];
	
	public: 	
		inline void init() {
			block_size = n;
			ans_tmp = INF;
			Get_Root(1, 1);
			tot[root] = 1;
			build(root, n);	
		}
		
		inline int query(int w, int rag) {
			int ret = Query(w, rag, q);
			for (int i=1,t;i<tot[w];i++) {
				t = rag - dis(fa[w][i], w);
				if (t >= 0) {
					ret += Query(fa[w][i], t, q);
					ret -= Query(fa[w][i-1], t, mul);
				}
			}
			return ret;
		}
	private:
		void Get_Root(int w, int f) {
			int mx = 0; sum[w] = 1;
			for (int i=head[w];i;i=nxt[i]) {
				if (to[i] != f && !vis[to[i]]) {
					Get_Root(to[i], w);
					mx = max(mx, sum[to[i]]);
					sum[w] += sum[to[i]];
				}
			}
			mx = max(block_size - sum[w], mx);
			if (mx < ans_tmp) {
				ans_tmp = mx;
				root = w;
			}
		}
		
		void build(int w, int sz) {
			vis[w] = 1; fa[w][0] = w;
			for (int i=head[w];i;i=nxt[i]) {
				if (!vis[to[i]]) {
					block_size = sum[to[i]] < sum[w] ? sum[to[i]] : sz - sum[w];
					ans_tmp = INF; Get_Root(to[i], w);
					memcpy(fa[root]+1, fa[w], sizeof(fa[w])-sizeof(int));
					tot[root] = tot[w] + 1;
					build(root, block_size);
				}
			}
			
			if (val[w]) {
				for (int i=0;i<tot[w];i++) 
					q[fa[w][i]].push_back(dis(w, fa[w][i]));
				for (int i=0;i<tot[w]-1;i++)
					mul[fa[w][i]].push_back(dis(w, fa[w][i+1]));	
			}
			sort(q[w].begin(), q[w].end());
			sort(mul[w].begin(), mul[w].end());
		} 
		
		inline int Query(int w, int r, vector<int> *a) {
			return upper_bound(a[w].begin(), a[w].end(), r) - a[w].begin();
		}
}PDC; 

class Virtual_Tree{
	int stk[N],rag[N],top,lca,cnt,root;
	queue<int> que;
	bool inq[N];
	
	public:	
		inline void build(int &tot) {
			cnt = tot; T = 0;
			root = p[1] = read(); 
			newnode(p[1], read());
			for (int i=2;i<=tot;i++) {
				p[i] = read();
				newnode(p[i], read());
				root = LCA(root, p[i]);
			}
			static auto cmp = [](int a, int b) {return num[a] < num[b];};
			sort(p+1, p+1+tot, cmp);
			if (root != p[1]) p[++tot] = root, newnode(root, -1);
			stk[top=1] = root;
			for (int i=1+(p[1]==root);i<=cnt;i++) {
				lca = LCA(p[i], stk[top]);
				for (;dep[stk[top]] > dep[lca];top--) 
					if (dep[stk[top-1]] >= dep[lca]) AddEdge(stk[top-1], stk[top]);
					else newnode(lca, -1), AddEdge(lca, stk[top]);
				if (lca != stk[top]) 
					stk[++top] = p[++tot] = lca;
				if (p[i] != stk[top])
					stk[++top] = p[i];
			}
			for (int i=1;i<top;i++)
				AddEdge(stk[i], stk[i+1]);
		}
		
		inline int solve(int tot) {
			prework(tot);
			int ret = 0;
			for (int i=1,u,v,r,mid,t;i<T;i+=2) {
				u = to[i]; v = to[i+1];
				r = rag[u] + rag[v] - cost[i] >> 1;
				if (r >= 0) {
					mid = move(u, v, r);
					ret -= PDC.query(mid, r);
				}
			} 
			for (int i=1;i<=tot;i++) 
				ret += PDC.query(p[i], rag[p[i]]);
			return ret;
		}
	private:
		inline void newnode(int w, int v) {
			rag[w] = v << 1;
			head[w] = 0;
		}
		
		inline int move(int x, int y, int r) {
			if (dep[x] < dep[y]) swap(x, y);
			r = rag[x] - r;
			for (int i=0;r;i++,r>>=1)
				if (r & 1) x = anc[x][i];
			return x;	 
		}
		
		inline void prework(int tot) {
			for (int i=1;i<=tot;i++) {
				que.push(p[i]);
				inq[p[i]] = 1;
			}
			
			while (!que.empty()) {
				int w = que.front(); 
				que.pop(); inq[w] = 0;
				for (int i=head[w];i;i=nxt[i]) {
					if (rag[w] > rag[to[i]] + cost[i]) {
						rag[to[i]] = rag[w] - cost[i];
						if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
					}
				}
			}
		}
		
		inline void AddEdge(int u, int v) {
			int w = dis(u, v);
			to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
			to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
		}
}VT; 

int main() {
	n = read();
	fill(val+1, val+1+n, 1);
	for (int i=1,lim=n,u,v;i<lim;i++) {
		u = read(); v = read();
		Add_Edge(u, ++n);
		Add_Edge(n, v);
	}
	
	DFS(1, 1);
	for (int j=1;j<=17;j++) {
		for (int i=1;i<=n;i++) {
			anc[i][j] = anc[anc[i][j-1]][j-1];
		}
	}
	PDC.init();
	
	m = read();
	for (int y=1,k;y<=m;y++) {
		VT.build(k = read());
		printf("%d\n",VT.solve(k)); 
	}
	return 0;
}

【BZOJ 2653】middle

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2653
神犇题解:http://blog.csdn.net/wzq_qwq/article/details/48809845

题解

先来考虑一个子问题:

假如序列左端点在[l1,r1]之间,右端点在[l2,r2]之间
给定中位数x,问能否找出一个区间使得中位数大于等于x

这个问题很简单的样子:将小于x的赋值-1,大于x赋值为1
这样问题就转化为能否找到一个区间使得区间和大于等于0
这个可以用线段树在 log(n) 的时间内处理

如何在可以接受的时间复杂度内搞出每一个中位数对应的那颗线段树
考虑将原序列排序后从小到大来建树
第i棵线段树和第i+1棵线段树就只有第i个位置需要从1变成-1
这个用函数式线段树就好啦!

Code

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

const int N = 25000 + 9;
const int M = 400000;

int n,m,tot,arr[N],_hash[N],last_ans;
vector<int> pos_que[N];

namespace Chair_Tree{
	#define CT Chair_Tree
	int ch[M][2],ls[M],rs[M],sum[M],root[N],cnt;
	
	void Build(int &w, int l, int r) {
		sum[w=++cnt] = r - l + 1;
		ls[w] = rs[w] = sum[w];
		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() {Build(root[1],1,n);}
	
	void insert(int p, int &w, int l, int r, int pur) {
		sum[w=++cnt] = sum[p] - 2;
		memcpy(ch[w],ch[p],sizeof(ch[w]));
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (pur < mid) insert(ch[p][0], ch[w][0], l, mid-1, pur);
			else insert(ch[p][1], ch[w][1], mid, r, pur);
			ls[w] = max(ls[ch[w][0]], sum[ch[w][0]] + ls[ch[w][1]]);
			rs[w] = max(rs[ch[w][1]], sum[ch[w][1]] + rs[ch[w][0]]);
		} else {
			ls[w] = rs[w] = 0;
		}		
	} inline void insert(int p, int w, int val) {
		insert(root[p],root[w],1,n,val);
	}
	
	int Get_sum(int w, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return sum[w];
		} else {
			int mid = l + r + 1 >> 1, ret = 0;
			if (L < mid) ret += Get_sum(ch[w][0], l, mid-1, L, R);
			if (mid <= R) ret += Get_sum(ch[w][1], mid, r, L, R);
			return ret;
		}
	} inline int Get_Sum(int w, int l, int r) {
		return Get_sum(root[w],1,n,l,r);
	}
	
	int query_left(int w, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return ls[w];
		} else {
			int mid = l + r + 1 >> 1;
			if (R < mid) return query_left(ch[w][0], l, mid-1, L, R);
			else if (mid <= L) return query_left(ch[w][1], mid, r, L, R);
			else {
				int t1 = query_left(ch[w][0], l, mid-1, L, mid-1);
				int t2 = query_left(ch[w][1], mid, r, mid, R) + Get_sum(ch[w][0], l, mid-1, L, mid-1);
				return max(t1, t2);
			}	
		}
	} inline int Left_Max(int w, int l, int r) {
		return query_left(root[w],1,n,l,r);
	}
	
	int query_right(int w, int l, int r, int L, int R) {
		if (L <= l && r <= R) {
			return rs[w];
		} else {
			int mid = l + r + 1 >> 1;
			if (R < mid) return query_right(ch[w][0], l, mid-1, L, R);
			else if (mid <= L) return query_right(ch[w][1], mid, r, L, R);
			else {
				int t1 = query_right(ch[w][1], mid, r, mid, R);
				int t2 = query_right(ch[w][0], l, mid-1, L, mid-1) + Get_sum(ch[w][1], mid, r, mid, R);
				return max(t1, t2);
			}
		}
	} inline int Right_Max(int w, int l, int r) {
		return query_right(root[w], 1, n, l, r);
	}
};

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

inline bool judge(int sta, int *lim) {
	int ret = CT::Get_Sum(sta, lim[2], lim[3]);
	ret += lim[1] < lim[2] ? CT::Right_Max(sta, lim[1], lim[2] - 1) : 0;
	ret += lim[3] < lim[4] ? CT::Left_Max(sta, lim[3] + 1, lim[4]) : 0;
	return ret >= 0;
}

int main() {
	n = read();
	for (int i=1;i<=n;i++) 
		arr[i] = _hash[i] = read();
	sort(_hash+1, _hash+1+n);
	tot = unique(_hash+1, _hash+1+n) - _hash - 1;
	for (int i=1;i<=n;i++) {
		arr[i] = lower_bound(_hash+1, _hash+1+tot, arr[i]) - _hash;
		pos_que[arr[i]].push_back(i);
	}
	CT::init();
	for (int i=2;i<=tot;i++) {
		CT::insert(i-1,i,pos_que[i-1][0]);
		for (int j=1,lim=pos_que[i-1].size();j<lim;j++) 
			CT::insert(i,i,pos_que[i-1][j]);
	}
	
	m = read();
	for (int i=1,lim[5],l,r,mid,ret;i<=m;i++) {
		for (int j=1;j<=4;j++)
			lim[j] = (read() + last_ans) % n + 1;
		sort(lim+1, lim+1+4);
		
		l = 1, r = tot;
		while (l <= r) {
			mid = l + r >> 1;
			if (!judge(mid,lim)) r = mid-1;
			else ret = mid, l = mid + 1; 
		}
		printf("%d\n",last_ans = _hash[ret]);
	}
	return 0;
}

【SOJ 1020】逆序对统计

题目传送门:http://oi.cdshishi.net:8080/Problem/1020

这货,本来以为是裸的主席树
结果被卡空间
最后还是只有写优化的主席树
另外,值域会爆int

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int M = 19000000;
const int N = 260000+9;

int n,m,POS[N],T;
LL vout,arr[N],NV[N],hash[N];

inline LL read(){
	char c=getchar(); LL 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 Chair_Tree{
	#define CT Chair_Tree
	#define lowbit(x) ((x)&-(x))
	int ch[M][2],sz[M],root[N*2],cnt,ans_tmp;
	
	void modify(int p, int &w, int v, int l, int r, int delta) {
		w = ++cnt; sz[w] = sz[p] + delta; 
		memcpy(ch[w],ch[p],sizeof(ch[w])); 
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (v < mid) modify(ch[p][0],ch[w][0],v,l,mid-1,delta);
			else modify(ch[p][1],ch[w][1],v,mid,r,delta);
		}	
	}
	
	inline void modify(int pos, int val, int delta){
		for (int i=pos;i<=n;i+=lowbit(i))
			modify(root[i],root[i],val,1,T,delta);
	}
	
	inline void build(){
		for (int i=1;i<=n;i++) 
			modify(root[i-1+n+1],root[i+n+1],arr[i],1,T,1);
	}
	
	void query(int w, int l, int r, int L, int R) {
		if (!w) return;
		else if (l <= L && R <= r) ans_tmp += sz[w];
		else {
			int mid = L + R + 1 >> 1;
			if (l < mid) query(ch[w][0],l,r,L,mid-1);
			if (mid <= r) query(ch[w][1],l,r,mid,R);
		}	
	}
	
	inline int query(int w, int l, int r) {
		ans_tmp = 0;
		query(w,l,r,1,T);
		return ans_tmp;
	}
	
	inline int query(int l ,int r, int L, int R){
		if (l > r || L > R) return 0; int ret = 0;
		for (int i=r;i;i-=lowbit(i)) ret += query(root[i],L,R);
		for (int i=l-1;i;i-=lowbit(i)) ret -= query(root[i],L,R);
		ret += query(root[n+r+1],L,R);
		ret -= query(root[n+l-1+1],L,R);
		return ret;
	}
};

int main(){
	n = read(); for (int i=1;i<=n;i++) arr[i] = hash[++T] = read(); 
	m = read(); for (int i=1;i<=m;i++) POS[i] = read(), NV[i] = hash[++T] = read();
	sort(hash+1,hash+1+T); T = unique(hash+1,hash+1+T) - hash - 1;
	for (int i=1;i<=n;i++) arr[i] = lower_bound(hash+1,hash+T+1,arr[i]) - hash;
	for (int i=1;i<=m;i++) NV[i] = lower_bound(hash+1,hash+T+1,NV[i]) - hash;
	
	CT::build();
	for (int i=1;i<=n;i++) vout += CT::query(1,i-1,arr[i]+1,T);
	for (int i=1,pos,nv;m;m--,i++) {
		pos = POS[i]; nv = NV[i];
		vout -= CT::query(1,pos-1,arr[pos]+1,T);
		vout -= CT::query(pos+1,n,1,arr[pos]-1);
		vout += CT::query(1,pos-1,nv+1,T);
		vout += CT::query(pos+1,n,1,nv-1);
		CT::modify(pos, arr[pos], -1);
		CT::modify(pos, nv, 1);
		arr[pos] = nv;
		cout<<vout<<endl;
	}
	return 0;
}

看其他人的代码,貌似还有非主席树的做法?
原来是不清真的分块…….E}QOU7H{JN1WP11[S43%HHR

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

【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六连测】[D4T2] 最短路

题目传送门:http://pan.baidu.com/s/1eRRG6Wy
离线版题目:http://paste.ubuntu.com/18687179/
数据传送门:http://pan.baidu.com/s/1qYtM8f6
数据生成器:http://paste.ubuntu.com/18687249/

唉,以前在CF上,看过这道题,拿到后,一眼就记得跟线段树有关,然而还是没有做出来QAQ
说一说怎么做:
如果边权很小,那么我们直接跑最短路就好,如果边权再大一点,那我们就写高精度
然而这题有2^100000,这个大概有10000那么多位(DEC),高精度会T,而且空间也开不下
所以只能搞神奇的技巧。
我们那函数式线段树来模拟二进制数组。那么单次修改就是log(n)的时间和空间复杂度
那么,比较大小怎么搞?搞一搞Hash,然后找到第一位不同的地方比较大小,仍然是log(n)
那么怎么进位?单点赋一,区间赋零即可,也为log(n)
然后就是码代码的事情了,我代码只写了一个小时,然而调试了3小时QAQ

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

const int MAXN = 200000+9;
const int MOD = 1000000000+7;
const int HASH = 9999971;
const int SEED = 137;
const int INF = 100000000;

int n,m,T,to[MAXN],head[MAXN],nxt[MAXN],cost[MAXN];
int s,t,done[MAXN],tpw[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;
}

namespace Chair_Tree{
	#define CT Chair_Tree
	#define N 10000000
	#define MX 200000
	int root[MAXN],hash[N],val[N],ch[N][2],MN[N];
	int ans_tmp,cnt;
	
	inline bool cmp(int w1, int w2){
		int l=1,r=MX,mid;
		while (l < r){
			mid = (l+r+1)/2;
			if (hash[ch[w1][1]] != hash[ch[w2][1]] || val[ch[w1][1]] != val[ch[w2][1]]) 
			w1 = ch[w1][1], w2 = ch[w2][1], l = mid;
			else w1 = ch[w1][0], w2 = ch[w2][0], r = mid-1; 
		}	
		return val[w1] > val[w2];
	}
	
	void find(int w, int l, int r, int pos){
		if (!w) ans_tmp = min(ans_tmp, l);
		else if (l >= pos) ans_tmp = min(ans_tmp, MN[w]);
		else if (r >= pos && l < r) {
			int mid = (l+r+1) / 2;
			if (pos < mid) find(ch[w][0], l, mid-1, pos);
			find(ch[w][1], mid, r, pos);
		}
	}inline int find(int w, int pos){ans_tmp = INF;find(w, 1, MX, pos);return ans_tmp;}	
	
	inline void maintain(int w, int l, int r){
		int len = (l+r+1)/2-l; MN[w] = INF;
		hash[w] = (LL)((LL)hash[ch[w][0]]+(LL)SEED*hash[ch[w][1]])*SEED % HASH;
		val[w] = (LL)((LL)val[ch[w][0]] + (LL)val[ch[w][1]]*tpw[len]) % MOD;
		if (ch[w][0]) MN[w] = min(MN[w], MN[ch[w][0]]);
		else MN[w] = min(MN[w], l);
		if (ch[w][1]) MN[w] = min(MN[w], MN[ch[w][1]]);
		else MN[w] = min(MN[w], (l+1+r)/2);
		if (l == r && !val[w]) MN[w] = min(MN[w], l);
	}
	
	void modify(int pre, int &w, int l, int r, int p){
		w = ++cnt; ch[w][0] = ch[pre][0]; ch[w][1] = ch[pre][1];
		if (l == r) hash[w] = 1, val[w] = 1, MN[w] = INF;
		else {
			int mid = (l+r+1) / 2;
			if (p < mid) modify(ch[pre][0], ch[w][0], l, mid-1, p);
			else modify(ch[pre][1], ch[w][1], mid, r, p);
			maintain(w,l,r);
		}
	}
	
	void clear(int pre, int &w, int l, int r, int L, int R){
		int mid = (l+r+1) / 2;
		if (L <= l && r <= R) w = 0;
		else {
			w = ++cnt; ch[w][0] = ch[pre][0]; ch[w][1] = ch[pre][1];
			if (L < mid) clear(ch[pre][0], ch[w][0], l, mid-1, L, R);
			if (R >= mid) clear(ch[pre][1], ch[w][1], mid, r, L, R);
			maintain(w,l,r);
		}  
	}
	
	inline int Add(int rt, int pos){
		int p1 = max(find(rt, pos),pos), ret;
		modify(rt, ret, 1, MX, p1);
		if (p1 > pos) clear(ret, ret, 1, MX, pos ,p1-1);
		return ret;
	}
	
	inline void output(int rt){
		printf("%d\n",val[rt]%MOD);
	}
	
	inline void print_path(){
		int w = t; cout<<t<<endl;
		while (w != s){
			for (int i=head[w];i;i=nxt[i]){
				int tmp = Add(root[to[i]], cost[i]);
				if (cmp(tmp,root[w])^cmp(root[w],tmp)==0) 
					w = to[i], cout<<w<<' '<<val[root[w]]<<endl;
			}
		}
		cout<<s;
	}
	
	void build(int &w, int l, int r){
		w = ++cnt; MN[w] = INF;
		if (l == r) hash[w] = val[w] = 1;
		else {
			int mid = (l+r+1)/2;
			build(ch[w][0], l, mid-1);
			build(ch[w][1], mid, r);
			maintain(w,l,r);
		}
	}inline int build_Tree(){int ret; build(ret,1,MX); return ret;}
};

struct DATA{
	int p,rt; DATA(){}
	DATA(int P, int RT):p(P),rt(RT){}
	bool operator < (const DATA &B) const {
		return CT::cmp(rt, B.rt);
	}
};
priority_queue<DATA> Q;

inline void AddEdge(int a, int b, int c){
	to[++T] = b; nxt[T] = head[a]; head[a] = T; cost[T] = c;
	to[++T] = a; nxt[T] = head[b]; head[b] = T; cost[T] = c;
}

inline void Dijkstra(){
	int tmp = CT::build_Tree();
	for (int i=1;i<=n;i++) CT::root[i] = tmp;
	CT::root[s] = 0;
	Q.push(DATA(s,CT::root[s]));
	
	while (!Q.empty()){
		DATA w = Q.top(); Q.pop();
		if (done[w.p]) continue;
		else if (w.p == t) {
			CT::output(w.rt);return;		
		} else {
			done[w.p] = 1;
			for (int i=head[w.p];i;i=nxt[i]){
				if (done[to[i]]) continue;
				else {
					tmp = CT::Add(w.rt,cost[i]);
					if (CT::cmp(CT::root[to[i]], tmp))
						CT::root[to[i]] = tmp, 
						Q.push(DATA(to[i], tmp));		
				}
			}	
		}
	}
	printf("-1\n");
}

int main(){
	freopen("shortest.in","r",stdin);
	freopen("shortest.out","w",stdout);
	n = read(); m = read();
	for (int i=1,a,b,c;i<=m;i++)
		a=read(), b=read(), c=read(),
		AddEdge(a, b, c+1);
	s = read(); t = read(); tpw[0] = 1; 
	for(int i=1;i<=150000;i++)
		tpw[i] = (LL)tpw[i-1]*2%MOD;
 	
	Dijkstra();
	
	return 0;
}

【NOI六连测】[D1T3] 联盟

题目传送门:http://pan.baidu.com/s/1kVjNeeV
离线版题目:http://paste.ubuntu.com/18671145/
数据传送门:http://pan.baidu.com/s/1qYRC8w8
数据生成器:http://paste.ubuntu.com/18671482/

先来说一说lcr的很好想的做法,分类讨论:
1)联盟的所有城市,有一些在首都的子树外,一些在首都的子树内
2)首都在联盟形成伞形内,且子树中,无联盟的城市
3)首都和联盟完全独立
然后是分类处理:
1)用主席树查一查,这个答案是0
2)树上倍增,再利用主席树查一查
3)直接lca搞一搞
lcr的code:http://paste.ubuntu.com/18671740/

然后是std的算法,分类讨论同lcr,做法稍有不同:
1)这个可以不用主席树查,我们使用DFS序,二分找到小于首都的DFS序最大的一个,然后+1,即可判断
2)这个,我们还是用DFS序,找到小于首都最大的那个,然后+1,那么这两个一定是卡得最紧的两个,然后用LCA更新答案
3)直接lca搞一搞

这两种算法优越在,分来讨论以后,把一个帮派缩成了一个代表城市
std的算法优越在,神奇的DFS序,DFS离得近就是夹得紧
另外这种题目,反正不是分类讨论乱搞,就是分治,以后还是要多推推式子
递归版本:http://paste.ubuntu.com/18670939/
非递归版本:

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

const int MAXN = 1000000+9;
const int INF = 100000000;

int n,T,head[MAXN],to[MAXN],nxt[MAXN],k,dep[MAXN],fa[MAXN][20],LC[MAXN];
int l[MAXN],r[MAXN],tot,cnt[MAXN],que[MAXN],*itr[MAXN],BUF[MAXN],now[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 AddEdge(int a, int b){
	to[++T] = b; nxt[T] = head[a]; head[a] = T;
	to[++T] = a; nxt[T] = head[b]; head[b] = T;
}

inline void DFS(){
	for (int i=1;i<=n;i++) now[i] = head[i];
	int w = 1; tot = 1;
	while (w) {
		if (!now[w]) {
			r[w] = tot;
			w = fa[w][0];
		} else {
			if (!l[w]) l[w] = ++tot;
			int tmp = to[now[w]]; now[w] = nxt[now[w]];
			if (dep[tmp] != dep[w]+1) continue;
			else w = tmp;
		}
	}
}

inline void BFS(){
	BUF[1] = 1; dep[1] = 1;
	for (int fro=1,bak=1;bak<=fro;bak++){
		int w = BUF[bak];
		for (int i=head[w];i;i=nxt[i]){
			if (!dep[to[i]]) dep[to[i]] = dep[w]+1,
			fa[to[i]][0] = w, BUF[++fro] = to[i];
		}
	}
}

inline bool cmp(const int &A, const int &B){
	return l[A] < l[B];
}

inline int find(int *arr, int ri, int val){
	if (l[arr[1]] >= val) return -1;
	else {
		int li=1,mid,ret;
		while (li <= ri){
			mid = (li+ri)/2;
			if (l[arr[mid]] < val) li=mid+1,ret=mid;
			else ri=mid-1;
		}
		return ret;
	}
}

inline int LCA(int a, int b){
	if (dep[a] < dep[b]) swap(a, b);
	for (int i=18;i>=0;i--)
		if (dep[fa[a][i]] >= dep[b]) 
			a = fa[a][i];
	if (a==b) return a;
	else {
		for (int i=18;i>=0;i--) if (fa[a][i] != fa[b][i])
			a = fa[a][i], b = fa[b][i];
		return fa[a][0];
	}
}	

inline void init_LCA(){
	for (int k=1;k<=18;k++)	for (int i=1;i<=n;i++)
		fa[i][k] = fa[fa[i][k-1]][k-1];
}

inline int DIS(int a, int b){
	int lca = LCA(a, b);
	return dep[a]+dep[b]-2*dep[lca];
}

inline void update(int *arr, int c, int v, int &ans, int lc){
	int lca = LCA(lc, v);
	if (lca == v) ans = min(ans, DIS(lc,v));
	else if (lca != v && lca != lc) ans = min(ans, dep[lc]+dep[v]-2*dep[lca]);
	else {
		int tmp = find(arr,c,l[v]);
		if (tmp==-1){
			if (l[arr[1]] <= r[v] && l[arr] > r[v]) ans = 0;
			else ans = min(ans, DIS(v,LCA(v,arr[1])));
		} else {
			if (tmp < c && l[arr[tmp+1]] <= r[v]) ans = 0;
			else {
				int lca = LCA(v,arr[tmp]);
				ans = min(dep[v]-dep[lca], ans);
				if (tmp < c){
					lca = LCA(v,arr[tmp+1]);
					ans = min(dep[v]-dep[lca], ans);
				}
			}
		}
	}
}

int main(){
	freopen("alliances.in","r",stdin);
	freopen("alliances.out","w",stdout);
	srand(19991226); n = read(); 
	for (int i=1;i<n;i++) AddEdge(read(),read());
	BFS(); DFS(); itr[1] = que; init_LCA();
	k = read(); for (int i=1;i<=k;i++) {
		cnt[i] = read(); 
		itr[i+1] = itr[i]+cnt[i];
		for (int j=1,tmp;j<=cnt[i];j++) itr[i][j] = read();
		int buf = itr[i][1];
		for (int j=2;j<=cnt[i];j++) buf = LCA(buf, itr[i][j]);
		LC[i] = buf; sort(itr[i]+1,itr[i]+cnt[i]+1,cmp);
	}
	
	for (int v,t,ans,Q=read();Q;Q--){
		v = read(); t=read(); ans = INF;
		for (int i=1,w;i<=t;i++){
			w = read(); 
			BUF[i] = itr[w][1];
			update(itr[w], cnt[w], v, ans, LC[w]);
		} 
		if (ans){
			int buf = BUF[1];
			for (int i=2;i<=t;i++) buf = LCA(buf, BUF[i]);
			sort(BUF+1,BUF+t+1,cmp), 
			update(BUF, t, v, ans, buf);
		}
		printf("%d\n",ans);
	}
	
	return 0;
} 

在%原教的代码的时候,发现了一点特殊的技能:
如果我们使用“当前弧”类似的技能,那么我们可以用一个BFS + while()很优雅的代替掉DFS()

【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