【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]$的边之后连通块的个数
这个我们将序列倍长,然后直接转化为原问题

【日常小测】String

题目大意

先给定一个长度为$n(n \le 50000)$的字符串$S$
之后给定$m(m \le 50000)$个操作(强制在线),操作分两种

  1. 在字符串$S$末尾加入一个字符
  2. 将$S$的子串$[l,r]$取出来,设为字符串$T$,询问$T$中出现至少两次的字符串的最长长度

解题报告

我们考虑用一棵线段树来支持插入斜率为$-1$的线段,并询问区间最值
这个是用来维护答案的,至于为什么插入的是线段,待会儿再说
至于具体实现,因为斜率相同,所以我们只需要将直线的纵截距插入即可,换言之我们只需要支持区间取$\max$即可

现在假设我们已经在维护了$[1,r-1]$的答案,并且我们在维护$[1,r]$回答所有右端点为$r$的询问
考虑插入第$r$个字符会影响哪些部分的答案:显然只会影响$fail$链上的答案
我们记录$last_x$表示$SAM$上的结点x代表的串在$S$中出现的最后一次的时间
我们注意到一条$fail$链上$last_x$一定是相等的,所以我们只需要考虑最长长度$l$
于是我们需要在线段树的$[last_x-l+1,last_x]$区间插入$x+y-(last_x+1)=0$的直线
之后我们更新$fail$链上的$last_x$,至于询问我们只需要到线段树上查询区间最值
当然维护$fail$树的话,我们需要使用$LCT$。

注意到$LCT$的一个$splay$里的$last_x$相等,所以单次$access$只会贡献$\log n$次区间取$\max$操作
所以我们已经能在$O(n \log ^2 n)$的时间复杂度内解决离线版本了
现在考虑在线版本,我们将线段树可持久化即可

【UOJ 77】A+B Problem

相关链接

题目传送门:http://uoj.ac/problem/77
神犇题解:http://www.cnblogs.com/geng4512/p/5296863.html

解题报告

我们发现如果忽略\(1<j<i\)这个限制,再假设\({l_i} = {r_i}\)
这样的话,直接上最小割就好

现在考虑\({l_i} < {r_i}\)
这样的话,用线段树优化建图就可以啦!

再考虑\(1<j<i\)这个限制
这样的话,用函数式线段树就可以啦!

感觉是VFK强行套数据结构啊!
另外还有BZOJ 3218可以双倍经验!
话说BZOJ上那些\(200ms+\)的神犇都是用的什么算法啊?
怎么这么快啊!

Code

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

const int N = 200000+9;
const int M = 2000000;
const int INF = 1000000000;

int n,m,S,T,vout,head[N],nxt[M],to[M],flow[M];
int tot,_hash[N],A[N],W[N],B[N],LL[N],RR[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, int f = INF, int t = 0) {
	static int E = 1; vout += f * t;
	to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
}

class Network_Flow{
    int cur[N],dis[N];
    queue<int> que;
    public:
        inline int MaxFlow() {
            int ret = 0;
            while (BFS()) {
                memcpy(cur, head, sizeof(head));
                ret += DFS(S, INF);
            }   
            return ret;
        }
    private:
        inline bool BFS() {
            memset(dis,60,sizeof(dis));
            que.push(S); dis[S] = 0;
              
            while (!que.empty()) {
                int w = que.front(); que.pop();
                for (int i=head[w];i;i=nxt[i]) {
                    if (dis[to[i]] > INF && flow[i]) {
                        dis[to[i]] = dis[w] + 1;
                        que.push(to[i]);
                    }
                }
            }
            return dis[T] < INF;
        }
        int DFS(int w, int f) {
            if (w == T) return f;
            else {
                int ret = 0;
                for (int tmp,&i=cur[w];i;i=nxt[i]) {
                    if (dis[to[i]] == dis[w] + 1 && flow[i]) {
                        tmp = DFS(to[i], min(f, flow[i])); 
                        flow[i] -= tmp; flow[i^1] += tmp;
                        f -= tmp; ret += tmp;
                        if (!f) break;
                    }
                }
                return ret;
            }
        }
}Dinic;

namespace Persistent_Segment_Tree{
	#define PST Persistent_Segment_Tree
	int ch[N][2],root[N],cnt,pur,sur,L,R;
	
	void insert(int p, int &w, int l, int r, int f = 0) {
		if (w = ++cnt, p) {
			ch[w][0] = ch[p][0];
			ch[w][1] = ch[p][1];
			Add_Edge(p, w);
		} 
		if (f) Add_Edge(w, f);
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (pur < mid) insert(ch[p][0], ch[w][0], l, mid-1, w);
			else insert(ch[p][1], ch[w][1], mid, r, w);
		} else Add_Edge(sur, w);
	}
	
	inline void insert(int p, int v) {
		pur = v; sur = p;
		insert(root[p-1], root[p], 1, tot);
	}
	
	void modify(int w, int l, int r) {
		if (!w) return;
		else if (L <= l && r <= R) Add_Edge(w, pur);
		else {
			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);
		}
	}
	
	inline void modify(int p, int node, int l, int r) {
		pur = node; L = l; R = r;
		modify(root[p], 1, tot);
	}
};

int main() {
	n = read(); PST::cnt = n << 1;
	S = 0; T = N - 1;
	for (int i=1;i<=n;i++) {
		_hash[++tot] = A[i] = read(); 
		B[i] = read();
		W[i] = read();
		_hash[++tot] = LL[i] = read();
		_hash[++tot] = RR[i] = read();
		P[i] = read();
	}
	sort(_hash+1, _hash+1+tot);
	tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
	for (int i=1;i<=n;i++) {
		A[i] = lower_bound(_hash+1, _hash+1+tot, A[i]) - _hash;
		LL[i] = lower_bound(_hash+1, _hash+1+tot, LL[i]) - _hash;
		RR[i] = lower_bound(_hash+1, _hash+1+tot, RR[i]) - _hash;
	}
	for (int i=1,l,r;i<=n;i++) {
		PST::insert(i, A[i]);
		Add_Edge(i, T, B[i], 1);
		Add_Edge(S, i, W[i], 1);
		PST::modify(i-1, i+n, LL[i], RR[i]);
		Add_Edge(i+n, i, P[i]);
	}
	printf("%d\n",vout-Dinic.MaxFlow());
	return 0;
}

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

【BZOJ 4408】[FJOI2016] 神秘数

链接

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

题解

假如我们给定一个已经排好序的序列{ai}
考虑神秘数产生的原因:\({a_i} > 1 + \sum\limits_{j = 1}^{i – 1} {{a_j}}\)

考虑给定的询问,如果使用函数式线段树进行处理,那么已经排好序了
现在的问题就是如何找到最小的、符合上述要求的\({a_i}\)

这货不满足二分的性质,所以不能用二分
然后我就不会做了 QwQ
这时,神犇ihopenot说:“直接暴力模拟就可以了啊!”
具体来说:

假设当前已经能够凑出1~i中的所有的数
统计1~(i+1)这个区间内所有数的和
如果等于i则停止,否则继续该操作

我们来考虑一下为什么这样做复杂度是正确的:

假设当前能凑出1~i,使用的最大的数为a
那么合法的下一个数一定在a+1到i+1之间
换一句话来说:进行一次增值操作可以“收割”长度为i-a的区间
更进一步:使用的数最小为a+2,能凑出的数至少为i+a+2
更进两步:下一次至少可以收割长度为i的区间
更进三步:每次收割区间的长度会增加ai,而且ai > a(i-1)+1
更进四步:仔细想一想,这货比Fibonacci数列增长还要快,所以至多进行log(n)次

然后这题就用函数式线段树来暴力迭代就可以辣!
这™是我第四次被Fibonacci数列坑了 QwQ
ps:这货貌似是双倍经验,参见BZOJ_4299

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 100000+9;
const int M = 3300000;
const int INF = 1e9;
 
int n,m,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 Chair_Tree{
    #define CT Chair_Tree
    int ch[M][2],sum[M],root[N];
    int ans_tmp,cnt;
     
    void insert(int p, int &w, int l, int r, int v) {
        w = ++cnt; sum[w] = sum[p] + v;
        memcpy(ch[w],ch[p],sizeof(ch[w]));
        if (l < r) {
            int mid = l + r + 1 >> 1;
            if (v < mid) insert(ch[p][0], ch[w][0], l, mid-1, v);
            else insert(ch[p][1],ch[w][1], mid, r, v);
        }   
    }
     
    inline void insert(int p, int v) {
        insert(root[p-1],root[p],1,INF,v);
    }
     
    void query(int p, int w, int l, int r, int v) {
        if (l == r) {
            ans_tmp += sum[w] - sum[p];
        } else {
            int mid = l + r + 1 >> 1;
            if (v < mid) query(ch[p][0],ch[w][0],l,mid-1,v);
            else {
                ans_tmp += sum[ch[w][0]] - sum[ch[p][0]];
                query(ch[p][1],ch[w][1],mid,r,v);
            }
        }
    }
     
    inline int query(int l, int r, int v) {
        ans_tmp = 0;
        query(root[l-1],root[r],1,INF,v);
        return ans_tmp;
    }
};
 
int main(){
    n = read();
    for (int i=1;i<=n;i++) { 
        arr[i] = read();
        CT::insert(i,arr[i]);
    }
         
    m = read();
    for (int j=1,l,r,cur,tmp;j<=m;j++) {
        l = read(); r = read(); cur = 0;
        while ((tmp = CT::query(l,r,cur+1)) > cur) {
            cur = tmp;
        }
        printf("%d\n",cur+1);
    }
    return 0;
}

【BZOJ 2006】[NOI2010] 超级钢琴

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2006
数据传送门:noi_2010_piano

这题很经典!很好!
首先肯定是求前缀和,然后搞n个结构体,第i个表示左端点在i的线段的最值
每次取出最大的结构体进行拓展,需要用函数式线段树来支持区间k大
时间复杂度:O(k*log(值域))
另外这题还有ST表的做法,但还不是很会 qwq

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

const int N = 500000+9;
const int M = 20000000+9;
const int BAS = 500000010;
const int INF = 1000010000;

int n,k,L,R,arr[N];
struct Query{
	int pos,num,val;
	bool operator < (const Query & B) const {
		return val < B.val;
	}
};
priority_queue<Query> que;

namespace Chair_Tree{
	#define CT Chair_Tree
	int ch[M][2],sum[M],cnt,root[N],ans_tmp;
	
	void insert(int p, int &w, int l, int r, int v) {
		w = ++cnt; sum[w] = sum[p] + 1;
		memcpy(ch[w],ch[p],sizeof(ch[0]));
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (v < mid) insert(ch[p][0], ch[w][0], l, mid-1, v);
			else insert(ch[p][1], ch[w][1], mid, r, v);
		} 
	} 
	
	inline void insert(int p, int w) {
		insert(root[p-1], root[p], 1, INF, w);
	} 
	
	void query(int p, int w, int l, int r, int num) {
		if (l == r) ans_tmp = l;
		else {
			int mid = l + r + 1 >> 1;
			if (sum[ch[w][1]] - sum[ch[p][1]] >= num) query(ch[p][1], ch[w][1], mid, r, num);
			else query(ch[p][0], ch[w][0], l, mid-1, num - (sum[ch[w][1]] - sum[ch[p][1]]));
		}
	}
	
	inline int query(int l, int r, int num) {
		query(root[l-1],root[r],1,INF,num);
		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(){
	n = read(); k = read(); L = read(); R = read();
	for (int i=1;i<=n;i++) arr[i] = arr[i-1] + read();
	for (int i=1;i<=n;i++) CT::insert(i,arr[i] + BAS);
	for (int i=1;i+L-1<=n;i++) {
		Query tmp; tmp.pos = i; tmp.num = 1;
		tmp.val = CT::query(i+L-1, min(n,i+R-1), 1) - BAS - arr[i - 1];
		que.push(tmp);
	}
	
	LL vout = 0;
	for (int i=1,p;i<=k;i++) {
		Query tmp = que.top(); que.pop();
		vout += tmp.val; 
		if (tmp.num < R - L + 1) {
			tmp.num++; p = tmp.pos;
			if (n - (p+L-1) + 1 < tmp.num) continue;
			tmp.val = CT::query(p+L-1, min(n,p+R-1), tmp.num) - arr[p - 1] - BAS;
			que.push(tmp);
		}
	}
	printf("%lld\n",vout);
	return 0;
}

【NOIP十连测】[D3T3] 序列

题目传送门:http://oi.cyo.ng/wp-content/uploads/2016/10/test3_problem.pdf
官方题解:http://oi.cyo.ng/wp-content/uploads/2016/10/solution.pdf

嗯,函数式线段树,挺好写的
但这™是NOIP模拟赛啊!

原始提问很简单,裸的函数式线段树
后来的更改,实际上就是求“询问区间包含p且询问值在数列的新旧值之间”的询问次数有多少
这样的话,可以打一打差分,然后也可以用函数式线段树搞
复杂度O(nlogn)

考试时候码的代码好丑啊……

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

const int N = 100000+9; 
const int M = 10000000;

int n,m,q,arr[N]; 
LL last_ans;
vector<int> Q_tmp[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 CT Segment_Tree
	int ch[M][2],sum[M],root[N],cnt,ans_tmp;
	
	void insert(int p, int &w, int l, int r, int pur) {
		w = ++cnt; 
		sum[w] = sum[p] + 1;
		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);
			}
		}
	} 
	
	inline void build_tree(){
		for (int i=1;i<=n;i++) {
			insert(root[i-1],root[i],1,n,arr[i]);
		}
	}
	
	void query(int w, int l, int r, int x, int f) {
		if (!w) {
			return;
		} else if (l < r){
			int mid = l + r + 1 >> 1;
			if (mid <= x) {
				query(ch[w][1],mid,r,x,f);
			} else {
				ans_tmp += sum[ch[w][1]]*f;
				query(ch[w][0],l,mid-1,x,f);
			} 
		} else if (l == r && l == x) {
			ans_tmp += sum[w]*f;
		} 
	}
	
	inline int query(int l, int r, int x) {
		ans_tmp = 0; 
		query(root[l-1],1,n,x,-1);
		query(root[r],1,n,x,1);
		return ans_tmp;
	}
	
	void modify(int p, int &w, int l, int r, int x, int f) {
		w = ++cnt;
		sum[w] = sum[p] + f; 
		memcpy(ch[w],ch[p],sizeof(ch[w]));
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (x < mid) {
				modify(ch[p][0],ch[w][0],l,mid-1,x,f);
			} else {
				modify(ch[p][1],ch[w][1],mid,r,x,f);
			}
		}
	}
	
	inline void rebuild(){
		memset(ch,0,sizeof(ch));
		memset(sum,0,sizeof(sum));
		memset(root,0,sizeof(root));
		cnt = 0;
		for (int i=1;i<=n;i++) {
			root[i] = root[i-1];
			for (int j=0,lim=Q_tmp[i].size();j<lim;j++) {
				int tmp = Q_tmp[i][j];
				if (tmp < 0) {
					modify(root[i],root[i],1,n,-tmp,-1);
				} else {
					modify(root[i],root[i],1,n,tmp,1);
				}
			}
		}
	}
	
	void ask(int w, int l, int r, int x) {
		if (!w) {
			return;
		} else if (l == r && r == x) {
			ans_tmp += sum[w];
		} else if (l < r) {
			int mid = l + r + 1 >> 1;
			if (x >= mid) {
				ask(ch[w][1],mid,r,x);
				ans_tmp += sum[ch[w][0]];
			} else {
				ask(ch[w][0],l,mid-1,x);
			}
		}
	}
	
	inline int requery(int p, int x) {
		ans_tmp = 0;
		ask(root[p],1,n,x);
		return ans_tmp;
	}
};

int main(){
	freopen("seq.in","r",stdin);
	freopen("seq.out","w",stdout);
	n = read(); m = read(); q = read();
	for (int i=1;i<=n;i++) {
		arr[i] = read();
	}
	CT::build_tree();
	for (int i=1,l,r,x;i<=m;i++) {
		l = read(); r = read(); x = read();
		last_ans += CT::query(l,r,x);
		Q_tmp[l].push_back(x);
		Q_tmp[r+1].push_back(-x);
	}
	CT::rebuild();
	printf("%lld\n",last_ans);
	for (int T=1,a,b;T<=q;T++) {
		a = read() ^ last_ans;
		b = read() ^ last_ans;
		last_ans += CT::requery(a,b);
		last_ans -= CT::requery(a,arr[a]);
		arr[a] = b;
		printf("%lld\n",last_ans);
	}
	return 0;
}

【BZOJ 4571】[SCOI2016] 美味

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4571

考试的时候,找了一个小时的规律,总觉得加法在二进制下有奇特的规律
考完试后知道真相的我,哭晕在厕所…

仍然考虑按位贪心
于是发现高位确定,低位不确定在十进制下是一个区间,于是搞一搞函数式线段树
仔细想一想,一般的Xor问题也可以这么做,trie树只是一个特殊的优化

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

const int N = 200000+9;
const int M = N * 18;

int arr[N],n,m,MX; 

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 Chair_Tree{
	#define CT Chair_Tree
	int ch[M][2],sum[M],cnt,root[N];
	int ans_tmp,L,R;
	
	void build(int p, int &w, int l, int r, int cur) {
		w = ++cnt; memcpy(ch[w],ch[p],sizeof(ch[w]));
		sum[w] = sum[p] + 1; if (l < r) {
			int mid = l + r + 1 >> 1;
			if (cur < mid) build(ch[p][0],ch[w][0],l,mid-1,cur);
			else build(ch[p][1],ch[w][1],mid,r,cur);
		}
	}
	
	inline void Build_Tree() {
		for (int i=1;i<=n;i++) 
			build(root[i-1],root[i],0,MX,arr[i]);
	}
	
	void ask(int w, int l, int r, int f) {
		if (L <= l && r <= R) ans_tmp += sum[w]*f;
		else if (w) {
			int mid = l + r + 1 >> 1;
			if (L < mid) ask(ch[w][0],l,mid-1,f);
			if (R >= mid) ask(ch[w][1],mid,r,f);
		}
	}
	
	inline int Query(int r1, int r2, int l, int r) {
		l = max(0,l); r = min(MX,r); 
		if (l > r) return 0;
		
		ans_tmp = 0; L = l; R = r;
		ask(r1,0,MX,-1); ask(r2,0,MX,1);
		return ans_tmp;
	}
	
	inline int query(int b, int x, int l, int r){
		int ret = 0, r1 = root[l-1], r2 = root[r];
		for (int i=17;~i;i--) {
			int c = (b & (1<<i)) ^ (1<<i); 
			if (Query(r1,r2,ret+c-x,ret+c+(1<<i)-1-x)) ret += c;
			else ret += c ^ (1<<i);
		} return ret^b;
	}
};

int main(){
	n = read(); m = read();
	for (int i=1;i<=n;i++) MX = max(MX, arr[i]=read());
	CT::Build_Tree();
	for (int i=1,b,x,l,r;i<=m;i++) {
		b = read(); x = read(); 
		l = read(); r = read();
		printf("%d\n",CT::query(b,x,l,r));
	}
	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;
}