【BZOJ 3881】[COCI2015] Divljak

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3881
神犇题解:http://trinkle.is-programmer.com/2015/6/30/bzoj-3881.100056.html

解题报告

考虑把Alice的串建成AC自动机
那么每一次用Bob的串去匹配就是Fail树上一些树链的并
这个用BIT+虚树无脑维护一下就可以了

Code

#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 2000009;
const int LOG = 26;
const int SGZ = 26;

int in[N];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

class Ac_Automaton{
int root, cnt, ch[N][SGZ], fail[N], pos[N], dep[N];
int head[N], to[N], nxt[N], ot[N], fa[N][LOG];
class FenwickTree{
int mx, sum[N];
public:
	inline void init(int nn) {
		mx = nn;
	}
	inline void modify(int p, int d) {
		for (int i = p; i <= mx; i += lowbit(i)) {
			sum[i] += d;
		}
	}
	inline int query(int l, int r) {
		int ret = 0;
		for (int i = l - 1; i > 0; i -= lowbit(i)) {
			ret -= sum[i];
		}
		for (int i = r; i; i -= lowbit(i)) {
			ret += sum[i];
		}
		return ret;
	}
private:
}bit;
public:
	inline void insert(char *s, int nn, int id) {
		int w = root;
		for (int i = 1; i <= nn; i++) {
			int cc = s[i] - 'a';
			if (!ch[w][cc]) {
				ch[w][cc] = ++cnt;
			}
			w = ch[w][cc];
		} 
		pos[id] = w;
	}
	inline void build() {
		static queue<int> que;
		for (int i = 0; i < SGZ; i++) {
			if (ch[root][i]) {
				que.push(ch[root][i]);
			}
		}
		for (; !que.empty(); que.pop()) {
			int w = que.front();
			AddEdge(fail[w], w);
			for (int i = 0; i < SGZ; i++) {
				if (!ch[w][i]) {
					ch[w][i] = ch[fail[w]][i];
				} else {
					que.push(ch[w][i]);
					fail[ch[w][i]] = ch[fail[w]][i];
				}
			}
		}
		DFS(0, 0);
		for (int j = 1; j < LOG; j++) {
			for (int i = 0; i <= cnt; i++) {
				fa[i][j] = fa[fa[i][j - 1]][j - 1];
			}
		}
		bit.init(cnt + 1);
	} 
	inline void match(char *s, int nn) {
		static vector<int> vt[N];
		static int que[N], stk[N], vis[N]; 
		int qtot = 0, stot = 0, vtot = 0;
		que[++qtot] = root;
		for (int i = 1, w = root; i <= nn; i++) {
			w = ch[w][s[i] - 'a'];
			que[++qtot] = w;
		}
		sort(que + 1, que + 1 + qtot);
		qtot = unique(que + 1, que + 1 + qtot) - que - 1;
		sort(que + 1, que + 1 + qtot, cmp);
		for (int i = 1; i <= qtot; i++) {
			if (stot) {
				int lca = LCA(que[i], stk[stot]);
				for (; stot && dep[stk[stot]] > dep[lca]; --stot) {
					if (stot > 1 && dep[stk[stot - 1]] >= dep[lca]) {
						vt[stk[stot - 1]].push_back(stk[stot]);
					} else {
						vt[lca].push_back(stk[stot]);
					}
				}
				if (stot && stk[stot] != lca) {
					stk[++stot] = lca;
					vis[++vtot] = lca;
				}
			} 
			stk[++stot] = que[i];
			vis[++vtot] = que[i];
		}
		for (; stot > 1; --stot) {
			vt[stk[stot - 1]].push_back(stk[stot]);
		}
		update(root, vt);
		for (int i = 1; i <= vtot; i++) {
			vt[vis[i]].clear();
		}
	}
	inline int query(int id) {
		return bit.query(in[pos[id]], ot[pos[id]]);
	}
private:
	inline void update(int w, vector<int> *vt) {
		for (int i = 0; i < (int)vt[w].size(); i++) {
			bit.modify(in[w], -1);
			bit.modify(in[vt[w][i]], 1);
			update(vt[w][i], vt);
		}
	}
	inline int LCA(int a, int b) {
		if (dep[a] < dep[b]) {
			swap(a, b);
		}
		for (int j = SGZ - 1; ~j; j--) {
			if (dep[fa[a][j]] >= dep[b]) {
				a = fa[a][j];
			}
		}
		if (a == b) {
			return a;
		}
		for (int j = SGZ - 1; ~j; j--) {
			if (fa[a][j] != fa[b][j]) {
				a = fa[a][j];
				b = fa[b][j];
			}
		}
		return fa[a][0];
	} 
	static bool cmp(int a, int b) {
		return in[a] < in[b];
	}
	inline void DFS(int w, int f) {
		static int tt = 0;
		in[w] = ++tt;
		dep[w] = dep[fa[w][0] = f] + 1;
		for (int i = head[w]; i; i = nxt[i]) {
			DFS(to[i], w);
		}
		ot[w] = tt;
	}
	inline void AddEdge(int u, int v) {
		static int E = 1;
		to[++E] = v; nxt[E] = head[u]; head[u] = E;
	}
}ac;

int main() {
	static char ss[N];
	int n = read();
	for (int i = 1; i <= n; i++) {
		scanf("%s", ss + 1);
		int len = strlen(ss + 1);
		ac.insert(ss, len, i);
	}
	ac.build();
	int m = read();
	for (int i = 1; i <= m; i++) {
		if (read() == 1) {
			scanf("%s", ss + 1);
			int len = strlen(ss + 1);
			ac.match(ss, len);
		} else {
			printf("%d\n", ac.query(read()));
		}
	}
	return 0;
}

【AtCoder】[Grand Contest 015 E] Mr.Aoki Incubator

相关链接

题目传送门:http://agc015.contest.atcoder.jp/tasks/agc015_e

解题报告

我们发现:对于任意一个时刻,一个病原体引发的感染者一定是一个区间
那么问题转化为选一些线段来覆盖整个序列,这个用可以线性维护
总的时间复杂度:$O(n \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;
 
const int N = 200009;
const int MOD = 1000000007;
 
int n, np[N], arr[N];
struct Data{
	int x, v; 
	inline bool operator < (const Data &D) const {
		return x < D.x || (x == D.x && v < D.v);
	}
}d[N], seg[N];
 
inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}
 
inline bool cmpv(int aa, int bb) {
	return d[aa].v < d[bb].v;
}
 
class Fenwick_Tree{
	int sum[N], uve, cur = 1;
public:
	inline void modify(int p, int x) {
		uve = (uve + x) % MOD;
		sum[p] = (sum[p] + x) % MOD;
	}	
	inline int query(int p) {
		while (cur < p) {
			++cur;
			sum[cur] = (sum[cur] + sum[cur - 1]) % MOD;
		}
		return ((uve - sum[p - 1]) + MOD) % MOD;
	}
}BIT;
 
int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		d[i].x = read();
		d[i].v = read();
		arr[i] = i;
	}
	sort(d + 1, d + 1 + n);
	sort(arr + 1, arr + 1 + n, cmpv);
	for (int i = 1; i <= n; i++) {
		np[arr[i]] = i;
	}
	for (int i = 1, cur = 0; i <= n; ++i) {
		seg[i].x = cur = max(cur, np[i]);
	}
	for (int i = n, cur = n + 1; i; --i) {
		seg[i].v = cur = min(cur, np[i]);
	}
	sort(seg + 1, seg + 1 + n);
	BIT.modify(1, 1);
	for (int i = 1; i <= n; i++) {
		int tmp = BIT.query(seg[i].v);
		BIT.modify(seg[i].x + 1, tmp);
	}
	printf("%d\n", BIT.query(n + 1));
	return 0;
}

【Codeforces 749E】Inversions After Shuffle

相关链接

题目传送门:http://codeforces.com/contest/749/problem/E
官方题解:http://codeforces.com/blog/entry/49186

解题报告

考虑从期望的定义下手
就是要求所有区间的逆序对的和
于是我们枚举右端点,然后算贡献
用$BIT$来维护,时间复杂度:$O(n \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 100009;

int n, p[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;
}

class Fenwick_Tree{
	double sum[N];
	public:
		inline void init() {
			memset(sum, 0, sizeof(sum));
		}
		inline void modify(int p, int d = 1) {
			for (int i = p; i <= n; i += lowbit(i)) {
				sum[i] += d;
			}
		}
		inline double query(int p) {
			double ret = 0;
			for (int i = p; i; i -= lowbit(i)) {
				ret += sum[i];
			}
			return ret;
		}
}BIT;

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		p[i] = read();
	}
	double ans = 0, psm = 0;
	for (int i = n; i; i--) {
		ans += BIT.query(p[i]);
		BIT.modify(p[i]);	
	}	
	ans *= n * (n + 1ll);
	BIT.init();
	for (int i = 1; i <= n; i++) {
		LL t1 = BIT.query(p[i]);
		LL t2 = i * (i - 1ll) / 2 - t1;
		ans += (psm += t1 - t2);
		BIT.modify(p[i], i);
	}
	printf("%.15lf\n", ans / n / (n + 1));
	return 0;
}

【BZOJ 4900】[CTSC2017] 密钥

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4900
原版题面:https://oi.qizy.tech/wp-content/uploads/2017/05/ctsc2017_day1.pdf

解题报告

我们做一个前缀和,发现问题变为询问一个区间内大于某个数的数有多少个
区间我们可以用滑动窗口来维护
询问大于某个数有多少可以用$BIT$来维护

总的时间复杂度:$O(n \log n)$
因为本题数据很水,所以过$10^7$的数据很轻松

当然标算是$O(n)$的算法
但我忘掉怎么证正确性了 qwq

Code

#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 40000009;

int k,n,seed,s,sum[N];
int ans1, ans2, ans3, MX, INF;
bool 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 int R() {
	seed = ((seed * 12321) ^ 9999) & 32767;
	return seed;
}

class Fenwick_Tree{
	int arr[N],tot;
	public:
		inline void modify(int pos, int delta) {
			tot += delta;
			for (int i = pos + MX; i <= INF; i += lowbit(i)) {
				arr[i] += delta;
			}
		}
		inline int query(int pos) {
			int ret = tot;
			for (int i = pos + MX; i > 0; i -= lowbit(i)) {
				ret -= arr[i];
			}
			return ret;
		}
}B1,B2;

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	k = read(); 
	seed = read();
	s = read();
	n = k * 2 + 1;
	int cnt = 0;
	for (int i = 1; i <= n; ++i) {
		p[i] = (R() >> 7) & 1;
		cnt += p[i];
	}
	int cur = 1;
	while (cnt > k) {
		while (!p[cur]) {
			++cur;
		}
		p[cur] = 0;
		--cnt;
	}
	while (cnt < k) {
		while (p[cur]) {
			++cur;
		}
		p[cur] = 1;
		++cnt;
	}
	for (int i=1;i<=n;i++) {
		p[i + n] = p[i];
	}
	
	for (int i = 1; i <= n * 2; ++i) {
		sum[i] = sum[i - 1] + (p[i]? 1: -1);
		MX = max(MX, abs(sum[i]));
	}
	INF = MX << 1;
	for (int i = 1; i <= n; i++) {
		if (p[i]) {
			B1.modify(sum[i], 1);
		} else {
			B2.modify(-sum[i], 1);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!p[i]) {
			int tmp = B1.query(sum[i]);
			if (tmp == 0) {
				ans1 = i;
			} else if (tmp == s) {
				ans2 = i;
			}
			B2.modify(-sum[i], -1);
			if (B2.query(-sum[i]) == s) {
				ans3 = i;
			}
			if (ans1 && ans2 && ans3) {
				break;
			}
		} else {
			B1.modify(sum[i], -1);
		}
		if (p[i + n]) {
			B1.modify(sum[i + n], 1);
		} else {
			B2.modify(-sum[i + n], 1);
		}
	}
	
	printf("%d\n%d\n%d", ans1, ans2, ans3);
	return 0;
}

【HDU 4630】No Pain No Game

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4630
神犇题解:http://www.cnblogs.com/zhsl/p/3234099.html

吐槽

最开始写了一个复杂度玄学的莫队,然后被卡$T$了
然后又写了一个$O(n \log n \sqrt{n \log n})$的$KD-Tree$,然后又被卡$T$了

然后看了题解就给跪了,这™不是傻逼题吗?

解题报告

我们将询问按照左端点排序,然后降序处理
这样每一次询问就相当于问一个后缀的前缀

然后考虑新加入最左边一个数$a_i$对于答案的影响
显然我们可以枚举因数$v$,然后记$v$上一次出现的位置为$last_v$
那么右端点在$i \sim last_v$之间的询问都会计算到这个$\gcd$
于是我们用$BIT$维护一个前缀最值就可以了
时间复杂度:$O(n \log^2 n)$

Code

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

const int N = 50009;

int n,m,pos[N],arr[N],last[N],ans[N];
struct Query{
	int l,r,id;
	inline bool operator < (const Query &Q) const {
		return l < Q.l;
	}
}q[N];
vector<int> que[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 Fenwick_Tree{
	#define lowbit(x) ((x)&-(x))
	int mx[N];
	public:
		inline void init() {
			memset(mx, 0, sizeof(mx));
		}
		inline void modify(int p, int v) {
			for (int i=p;i<=n;i+=lowbit(i)) {
				mx[i] = max(mx[i], v);
			}
		}
		inline int query(int p) {
			int ret = 1;
			for (int i=p;i;i-=lowbit(i)) {
				ret = max(ret, mx[i]);
			}
			return ret;
		}
}BIT;

int main() {
	for (int T=read();T;T--) {
		n = read();
		for (int i=1;i<=n;i++) {
			que[i].clear();
			arr[i] = read();
			pos[arr[i]] = i; 
		}
		for (int i=2;i<n;i++) {
			for (int j=i;j<=n;j+=i) {
				que[pos[j]].push_back(i);
			}
		} 
		m = read();
		for (int i=1,l,r;i<=m;i++) {
			q[i].l = read();
			q[i].r = read();
			q[i].id = i;
		}
		sort(q+1, q+1+m);
		BIT.init();
		memset(last,60,sizeof(last));
		for (int i=m,cur=n+1;i;i--) {
			while (cur > q[i].l) {
				--cur;
				for (int j=0;j<que[cur].size();j++) {
					int v = que[cur][j];
					if (last[v] <= n) {
						BIT.modify(last[v], v);
					}
					last[v] = cur;
				}
			}
			if (q[i].l == q[i].r) ans[q[i].id] = 0;
			else ans[q[i].id] = BIT.query(q[i].r);
		}
		for (int i=1;i<=m;i++) {
			printf("%d\n",ans[i]);
		}
	}
	return 0;
}

【BZOJ 4231】回忆树

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4231
数据生成器:http://paste.ubuntu.com/24366714/
神犇题解:http://www.cnblogs.com/clrs97/p/5467637.html

解题报告

首先我们如果最终一个串出现的位置会越过$LCA$
那么我们可以把这一部分的情况单独拿出来,暴力跑$KMP$

剩下就是单纯地从根节点向下,或者向上的路径中出现了多少次
这不难让我们想到广义后缀自动机,但似乎这题并不能用

考虑另一个方法,把所有模式串建成AC自动机
然后在原树上$DFS$,进入一个点时将其在AC自动机对应的结点权值$+1$
退出来的时候将其$-1$,那么我们在需要询问的时候统计一下子树的权值和就可以了

总时间复杂度:$O(n \log n + \sum |S|)$

Code

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

const int N = 100009;
const int M = 600009;

int n,m,head[N],nxt[M],to[M],cost[M],U[N];
int pp[N][2],ans[N],dep[N],fa[N][20],C[N];
vector<pair<int,int> > qry[N]; 

class AC_Automaton{
	int dfs_cnt,ch[M][26],fail[M],in[M],out[M];
	queue<int> que; vector<int> sn[M]; 
	struct Fenwick_Tree{
		int sum[M],sz;
		inline int lowbit(int x) {return x & -x;}
		inline void modify(int w, int delta) {
			for (int i=w;i<=sz;i+=lowbit(i)) sum[i] += delta;
		}
		inline int query(int l, int r) {
			int ret = 0; l--;
			for (int i=l;i;i-=lowbit(i)) ret -= sum[i];
			for (int i=r;i;i-=lowbit(i)) ret += sum[i];
			return ret;
		}
	}BIT;
	public:
		inline void build() {
			for (int i=0;i<26;i++) ch[0][i]=1;
			que.push(1); fail[1] = 0;
			while (!que.empty()) {
				int w = que.front(); que.pop();
				sn[fail[w]].push_back(w);
				for (int i=0;i<26;i++) {
					if (ch[w][i]) {
						que.push(ch[w][i]);
						fail[ch[w][i]] = ch[fail[w]][i];
					} else ch[w][i] = ch[fail[w]][i];
				}
			}
			DFS(1);
			BIT.sz = dfs_cnt;
		}
		inline int insert(char *s) {
			static int cnt = 1;
			int w = 1, len = strlen(s+1);
			for (int i=1,c;i<=len;i++) {
				if (!ch[w]-'a']) ch[w] = ++cnt;
				w = ch[w]; 
			} 
			return w;
		}
		inline int query(int p) {
			return BIT.query(in[p], out[p]);
		}
		inline void modify(int p, int delta) {
			BIT.modify(in[p], delta);
		}
		inline int move(int w, int c) {
			return ch[w];
		}
	private:
		void DFS(int w) {
			in[w] = ++dfs_cnt;
			for (int i=sn[w].size()-1;~i;i--)
				if (!in[sn[w][i]]) DFS(sn[w][i]);
			out[w] = dfs_cnt;
		}
}ac;

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 AddEdge(int u, int v, int c) {
	static int E = 1; cost[E+1] = cost[E+2] = c;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

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

void pre(int w, int f) { 
	fa[w][0] = f; dep[w] = dep[f] + 1;
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f) 
		C[to[i]] = cost[i], pre(to[i], w);
}

void solve(int w, int p) { 
	for (int i=qry[w].size()-1,f;~i;i--) {
		if (qry[w][i].first>0) f = 1; else f = -1, qry[w][i].first *= -1;
		ans[qry[w][i].first] += ac.query(pp[qry[w][i].first][qry[w][i].second]) * f;
	}
	for (int i=head[w],tmp;i;i=nxt[i]) {
		if (dep[to[i]] > dep[w]) {
			tmp = ac.move(p, cost[i]); 
			ac.modify(tmp, 1); 
			solve(to[i], tmp);
			ac.modify(tmp, -1); 
		}
	}
}

inline int dif(int &u, int &v, int lca, char *s, int len) {
	static char ss[M]; static int NXT[M]; int tot = 0, TOT;
	int w = u, l = dep[u] - dep[lca] - len + 1, ret = 0;
	if (l > 0) {for (int j=0;l;l>>=1,++j) if (l&1) w = fa[w][j]; u = w;} 
	while (w != lca) ss[++tot] = C[w] + 'a', w = fa[w][0];
	w = v; l = dep[v] - dep[lca] - len + 1;
	if (l > 0) {for (int j=0;l;l>>=1,++j) if (l&1) w = fa[w][j]; v = w;}
	TOT = (tot += dep[w] - dep[lca]);
	while (w != lca) ss[tot--] = C[w] + 'a', w = fa[w][0];
	
	for (int i=1,w;i<=len;i++) {
		for (w=NXT[i];w&&s[w+1]!=s[i+1];w=NXT[w]);
		NXT[i+1] = w + (s[w+1] == s[i+1]);
	}
	for (int i=1,w=0;i<=TOT;i++) {
		for (;w&&s[w+1]!=ss[i];w=NXT[w]);
		w += s[w+1] == ss[i];
		ret += w == len;
	} 
	return ret;
}

int main() {
	n = read(); m = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		char c[2]; scanf("%s",c);
		AddEdge(u, v, c[0] - 'a');
	} 
	pre(1, 1); 
	for (int j=1;j<=19;j++) 
		for (int i=1;i<=n;i++) 
			fa[i][j] = fa[fa[i][j-1]][j-1];
	char pat[300009];
	for (int i=1,u,v,lca,ll,p1,p2;i<=m;i++) {
		U[i] = u = read(); v = read(); lca = LCA(u, v);
		scanf("%s",pat+1); pp[i][0] = ac.insert(pat); ll = strlen(pat+1);
		qry[u].push_back(make_pair(i,1)); qry[v].push_back(make_pair(i,0)); 
		ans[i] += dif(u, v, lca, pat, ll); 
		qry[u].push_back(make_pair(-i,1)); qry[v].push_back(make_pair(-i,0));
		for (int l=1,r=ll;l<r;l++,r--) swap(pat[l], pat[r]); pp[i][1] = ac.insert(pat);
	} 
	ac.build();
	solve(1, 1);
	for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

【CodeChef TREEP】Period on tree

相关链接

题目传送门:https://www.codechef.com/NOV15/problems/TREEP
中文题面:http://www.codechef.com/download/translated/NOV15/mandarin/TREEP.pdf
官方题解:https://discuss.codechef.com/questions/76897/treep-editorial

题目大意

给定一个$n(n \le 200000)$个结点的树,每条边上有一个小写字母
定义$Str_{u,v}$为从$u$走到$v$将路径上的小写字母按顺序拼起来组成的字符串
给定$m(m \le 200000)$个操作,操作分两类:

  1. 输入$u,v$,询问$Str_{u,v}$的循环节最短为多长
  2. 输入$u,v,c$,表示将$u \to v$这条边上的字符改成$c$

解题报告

这么奇怪的题目,一看就只能是$Hash$来做
我们不难发现,若循环节为$l$,串长$len$,那么$\forall x \in (l,len]$若$x \equiv 0(\bmod l)$则$x$也是循环节
于是如果我们可以$O(\log n)$判定$l$是不是原串的循环节,我们就可以在$O(n \log^2 n)$的时间复杂度内解决这个问题了

我们发现,若是循环节,那么开头那一段的$Hash$值不仅可以整除整个串的$Hash$值,而且等于一个等比数列
于是我们就可以用BIT维护一个到根的前缀和,然后将判定优化到$O(\log n)$

Code

这是考试的代码,似乎没写多组数据,CC上交不了QwQ

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 200009;
const int M = N << 1;
const int SED = 37;
const int MOD = 1000000009;
 
int n,m,head[N],to[M],nxt[M],cost[M],dep[N],beg[N],END[N]; 
int POW[M],tot,pri[N],vis[N],sur[N],fa[N][20],val[N];
char pat[5];
 
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;
}
 
inline void AddEdge(int u, int v, int c) {
    static int E = 1; cost[E+1] = cost[E+2] = c;
    to[++E] = v; nxt[E] = head[u]; head[u] = E;
    to[++E] = u; nxt[E] = head[v]; head[v] = E;
}
 
class FenwickTree{
    #define lowbit(x) ((x)&(-(x)))
    int sum[N];
    public:
        inline void modify(int l, int r, int v) {
            for (int i=l-1;i;i-=lowbit(i)) sum[i] = (sum[i] - v) % MOD;
            for (int i=r;i;i-=lowbit(i)) sum[i] = (sum[i] + v) % MOD;
        }   
        inline int query(int p) {
            int ret = 0; p = beg[p];
            for (int i=p;i<=n;i+=lowbit(i)) 
                ret = (ret + sum[i]) % MOD;
            return (ret + MOD) % MOD;
        }
}up,dw;
 
inline void prework() {
    POW[0] = sur[1] = 1; 
    for (int i=1;i<M;i++) POW[i] = (LL)POW[i-1] * SED % MOD;
    for (int i=2;i<N;i++) {
        if (!vis[i]) pri[++tot] = i, sur[i] = i;
        for (int j=1;j<=tot&&i*pri[j]<N;j++) {
            vis[i*pri[j]] = 1; sur[i*pri[j]] = pri[j];
            if (i % pri[j] == 0) break;
        }
    }
}
 
inline int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int j=19;~j;j--) if (dep[fa[u][j]]>=dep[v]) u=fa[u][j];
    if (u == v) return u;
    for (int j=19;~j;j--) if (fa[u][j]!=fa[v][j]) u=fa[u][j],v=fa[v][j];
    return fa[u][0];
}
 
void DFS(int w, int f) {
    static int dfs_cnt = 0; 
    beg[w] = ++dfs_cnt;
    fa[w][0] = f; dep[w] = dep[f] + 1;
    for (int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            val[to[i]] = cost[i];
            DFS(to[i], w);
        }
    }
    END[w] = dfs_cnt;
    up.modify(beg[w], END[w], (LL)val[w] * POW[n-dep[w]+1] % MOD);
    dw.modify(beg[w], END[w], (LL)val[w] * POW[dep[w]] % MOD); 
}
 
inline int FA(int u, int k) {
    for (int t=0;k;k>>=1,t++) 
        if (k&1) u = fa[u][t];
    return u;
}
 
inline int query(int u, int v, int lca, int k) {
    if (dep[u] - dep[lca] >= k) {
        int ret = (up.query(u) - up.query(FA(u, k))) % MOD;
        return (((LL)ret * POW[dep[u]-1] % MOD) + MOD) % MOD;
    } else {
        int ret = (up.query(u) - up.query(lca)) % MOD;
        ret = (LL)ret * POW[dep[u] - 1] % MOD;
        int res = dep[u] + dep[v] - (dep[lca] << 1) - k;
        res = (dw.query(FA(v, res)) - dw.query(lca)) % MOD;
        res = (LL)res * POW[n + dep[u] - (dep[lca] << 1) - 1] % MOD;
        return ((res + ret) % MOD + MOD) % MOD;
    }
}
 
inline int Pow(int w, int t) {
    int ret = 1;
    for (;t;t>>=1,w=(LL)w*w%MOD)
        if (t&1) ret=(LL)ret*w%MOD;
    return ret;
}   
 
inline int query(int u, int v) {
    int lca = LCA(u, v); tot = 0;
    int len = dep[u] + dep[v] - (dep[lca] << 1);
    int STA = query(u, v, lca, len), ori = len;
    for (int c,w=len;c=sur[w],w>1;) {
        pri[++tot] = c; vis[tot] = 0;
        for (;w%c==0;w/=c) vis[tot]++; 
    }
    for (int i=1,sta,cur,PRI;i<=tot;i++) {
        PRI = pri[i];
        for (int j=1;j<=vis[i];j++) {
            sta = (LL)(Pow(POW[len/PRI], ori/len*PRI) - 1) * Pow(POW[len/PRI]-1, MOD-2) % MOD;
            cur = (LL)STA * Pow(query(u, v, lca, len / PRI), MOD-2) % MOD;
            if (sta==cur) len /= PRI;
            else break;
        }
    }
    return len;
}
 
int main() {
    prework();
    n = read(); 
    for (int i=1,u,v;i<n;i++) {
        u = read(); v = read();
        scanf("%s",pat+1);
        AddEdge(u, v, pat[1]-'a'+1);
    }
    DFS(1, 1);
    for (int j=1;j<20;j++) {
        for (int i=1;i<=n;i++) {
            fa[i][j] = fa[fa[i][j-1]][j-1];
        }
    } 
    m = read(); 
    for (int i=1,u,v,c;i<=m;i++) {
        if (read() == 1) {
            u = read(); v = read();
            printf("%d\n",query(u, v));
        } else {
            u = read(); v = read();
            if (dep[u] > dep[v]) swap(u, v);
            scanf("%s",pat+1); c = pat[1]-'a'+1;
            if (c == val[v]) continue;
            up.modify(beg[v], END[v], (LL)(c - val[v]) * POW[n-dep[v]+1] % MOD);
            dw.modify(beg[v], END[v], (LL)(c - val[v]) * POW[dep[v]] % MOD);
            val[v] = c;
        }
    } 
    return 0;
}

【日常小测】链上求和

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/03/3764237472378947264.png
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/03/4876274224.jpg

解题报告

这题就是暴力写出来之后,发现可以直接维护一个东西
于是维护一个子树和,然后支持一下换根的操作就可以辣!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
  
const int N = 100009;
const int M = N << 1;
const int MOD = 1000000007;
  
int n,vout,head[N],to[M],nxt[M],val[N];
int tot,fa[N],yzq_in[N],yzq_out[N],sz[N];
struct Query{int v,id;}q[N];
  
class Fenwick_Tree{
    #define lowbit(x) ((x)&-(x))
    public:
        int sum[N],SUM;
        inline void modify(int p, int v) {
            for (int i=p;i<=n;i+=lowbit(i)) sum[i] = (sum[i] + v) % MOD;
            SUM = (SUM + v) % MOD;
        } 
        inline void modify(int l, int r, int v) {
            for (int i=r;i;i-=lowbit(i)) sum[i] = (sum[i] + v) % MOD;
            for (int i=l-1;i;i-=lowbit(i)) sum[i] = (sum[i] - v) % MOD;
        }
        inline int query(int l, int r) {
            int ret = 0;
            for (int i=r;i;i-=lowbit(i)) ret = (ret + sum[i]) % MOD;
            for (int i=l-1;i;i-=lowbit(i)) ret = (ret - sum[i]) % MOD;
            return (ret + MOD) % MOD;
        }
        inline int query(int p) {
            int ret = 0;
            for (int i=p;i<=n;i+=lowbit(i)) ret = (ret + sum[i]) % MOD;
            return (ret + MOD) % MOD;
        }
}BIT,BIT2,BIT3;
  
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;
}
  
inline void Add_Edge(int u, int v) {
    static int E = 1;
    to[++E] = v; nxt[E] = head[u]; head[u] = E;
    to[++E] = u; nxt[E] = head[v]; head[v] = E;
}
  
inline bool cmp(const Query &A, const Query &B) {
    return A.v < B.v || (A.v == B.v && A.id < B.id);
}
  
void DFS(int w, int f) {
    fa[w] = f; yzq_in[w] = ++tot; sz[w] = 1;
    for (int i=head[w];i;i=nxt[i]) {
        if (to[i] != f) {
            DFS(to[i], w);
            sz[w] += sz[to[i]];
        }
    }
    yzq_out[w] = tot;
}   
  
inline void solve(int w) {
    int ret = 0; LL cur=1,s1;
    for (int i=head[w],s,c;i;i=nxt[i]) {
        if (to[i] == fa[w]) {
            s = (BIT.SUM - BIT.query(yzq_in[w], yzq_out[w])) % MOD; 
            s1 = BIT3.query(yzq_in[w]);
            c = BIT2.query(yzq_in[w]);
            s = (s - s1 + (LL)c * n) % MOD;
            ret = (ret + (LL)sz[w] * s) % MOD; 
            ret = (ret + (LL)(n - sz[w]) * cur) % MOD;
            cur += n - sz[w];
        } else {
            ret = (ret + (LL)(n-sz[to[i]]) * BIT.query(yzq_in[to[i]], yzq_out[to[i]])) % MOD;
            ret = (ret + (LL)sz[to[i]] * cur) % MOD;
            cur += sz[to[i]];
        }
    }
    vout = (vout + (LL)ret * val[w]) % MOD;
}
 
int main() {
    n = read();
    for (int i=1;i<n;i++) Add_Edge(read(), read());
    for (int i=1;i<=n;i++) val[i] = q[i].v = read(), q[i].id = i;
    DFS(1, 1); sort(q+1, q+1+n, cmp);
    for (int i=1,p,v;i<=n;i++) {
        p = q[i].id;
        solve(p);
        BIT.modify(yzq_in[p], sz[p]);
        BIT2.modify(yzq_in[p], yzq_out[p], 1);
        BIT3.modify(yzq_in[p], yzq_out[p], sz[p]);
        for (int j=head[p],t;j;j=nxt[j]) {
            if ((t=to[j]) != fa[p]) 
                BIT3.modify(yzq_in[t], yzq_out[t], sz[t]);
        }
    }
    printf("%d\n",(vout+MOD)%MOD);
    return 0;
}

【BZOJ 4282】慎二的随机数列

相关链接

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

解题报告

首先我们需要得到一个结论:一定存在一组最优解,使得所有的模糊的位置均在LIS中
现在我们来证明一下这个结论:

考虑如果有一组最优解中存在一个模糊的位置不在最优解中
那么讲这个模糊的位置换成后面的第一个确定位置的数即可,这样不会使答案变劣

于是我们就假设一个确定的位置的前缀中有a个不确定位置
那么我们把该确定位置的值减去a(相当于把那a个不确定位置在值域上留出位置)
然后对确定的串做一次LIS,然后加上不确定位置的个数即可

Code

我写LIS一直用的BIT,但PoPoQQQ大爷的LIS似乎更加优雅
他是直接维护一个最优的LIS,然后每一次lower_bound就可以了!

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

const int N = 200000+9;

int n,m,tot,vout,_hash[N],f[N],arr[N];
char pat[10];

class Fenwick_Tree{
	int mx[N];
	public:
		inline void modify(int p, int v) {
			for (int i=p;i<=tot;i+=lowbit(i))
				mx[i] = max(mx[i], v);
		}
		inline int query(int p) {
			int ret = 0; 
			for (int i=p-1;i;i-=lowbit(i))
				ret = max(ret, mx[i]);
			return ret;
		}
	private:
		inline int lowbit(int x) {
			return x & (-x);
		}
}BIT;

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

int main() {
	n = read();
	for (int i=1;i<=n;++i) {
		scanf("%s",pat+1);
		if (pat[1] == 'K') {
			arr[++tot] = read() - m;
			_hash[tot] = arr[tot];		
		} else ++m;
	}
	n = tot; sort(_hash+1, _hash+1+tot);
	tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
	for (int i=1;i<=n;i++) {
		arr[i] = lower_bound(_hash+1, _hash+1+tot, arr[i]) - _hash;
		f[i] = BIT.query(arr[i]) + 1;
		vout = max(f[i], vout);
		BIT.modify(arr[i], f[i]);
	} 
	printf("%d\n",vout + m);
	return 0;
}

【AtCoder】[Regular Contest 068 E] Snuke Line

相关链接

题目传送门:http://arc068.contest.atcoder.jp/tasks/arc068_c
数据生成器:http://paste.ubuntu.com/23948002/
官方题解:https://arc068.contest.atcoder.jp/editorial

解题报告

设一个间隔$d$,一种物品的覆盖区间长度为$L$
若 $L \ge d$ 则一定能取,否则只会被遍历到一次
于是我们就从小到达枚举$d$,同时维护$L$,把$L < d$的扔到$BIT$里就可以啦!
复杂度: $O(n{log^2}n)$,不过因为$BIT$的常数关系,所以跑得飞快

Code

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

const int N = 300000+9;

int n,m;
struct Event{
	int l,r,len;
	inline Event() {}
	inline Event(int _l, int _r) {l = _l; r = _r; len = r - l + 1;}
	inline bool operator < (const Event &B) const {return len < B.len;}
}e[N];

class Fenwick_Tree{
	int cnt[N];
	public:
		inline void modify(int l, int r) {
			for (int i=l-1;i;i-=lowbit(i)) cnt[i]--;
			for (int i=r;i;i-=lowbit(i)) cnt[i]++; 
		}
		inline int query(int p) {
			int ret = 0;
			for (int i=p;i<=m;i+=lowbit(i)) ret += cnt[i];
			return ret;
		}
	private:
		inline int lowbit(int x) {
			return x & -x;
		}
}BIT; 

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

int main() {
	n = read(); m = read();
	for (int i=1,l,r;i<=n;i++) {
		l = read(); r = read();
		e[i] = Event(l, r);
	}
	sort(e+1, e+1+n);
	for (int d=1,p=1,sta=n;d<=m;d++) {
		for (;p<=n&&e[p].len==d-1;p++) {
			--sta;
			BIT.modify(e[p].l, e[p].r);
		}
		int vout = 0;
		for (int i=d;i<=m;i+=d) 
			vout += BIT.query(i);
		printf("%d\n",vout+sta);
	}
	return 0;
}

【BZOJ 4361】isn

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4361
数据传送门:https://oi.qizy.tech/?attachment_id=1898

题解

考虑一个长度为i的非下降子序列
如果忽略成为非下降子序列就停止的限制
那么其对于答案的贡献为g[i]*(n-i)!

现在考虑成为非下降子序列就停止的限制
对于长度为i的非下降子序列,非法的话,一定是从i+1的序列删掉一个数
所以减掉\(g[i + 1] \cdot (n – (i + 1))! \cdot (i + 1)\)即可

至于为什么这样会不重不漏、刚好删掉所有非法方案?
唯一的疑惑就在于有一些方案不在第一次非法时删除
但不难发现将第一段+第二段看成一个操作的话
每一个操作刚好不重不漏加上了所有的合法方案

代码

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

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

int tot,n,_hash[N],arr[N],f[N],POW[N]; 

namespace Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define lowbit(x) ((x)&-(x))
	int cnt[N][N];
	
	inline void insert(int t, int p, int delta) {
		for (int i=p;i<=n;i+=lowbit(i)) 
			(cnt[t][i] += delta) %= MOD;
	}
	
	inline int query(int t, int p) {
		int ret = 0;
		for (int i=p;i;i-=lowbit(i))
			(ret += cnt[t][i]) %= MOD;
		return ret;
	} 
};

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();
	for (int i=1;i<=n;i++) 
		_hash[i] = arr[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;
	POW[1] = POW[0] = 1;
	for (int i=2;i<=n;i++) 
		POW[i] = (LL)POW[i-1] * i % MOD;
	
	for (int i=1;i<=n;i++) {
		for (int j=n,tmp;j>1;j--) {
			tmp = BIT::query(j-1,arr[i]);
			(f[j] += tmp) %= MOD;
			BIT::insert(j,arr[i],tmp);
		}
		BIT::insert(1,arr[i],1);
		f[1]++;
	} 
	
	int vout = 0;
	for (int i=1;i<=n;i++) {
		(vout += (LL)f[i] * POW[n-i] % MOD) %= MOD;
		if (i < n) 
			(vout -= ((LL)f[i+1] * POW[n-i-1] % MOD) * (i+1) % MOD) %= MOD;
	}
	printf("%d\n",(vout+MOD)%MOD);
	return 0;
}

【UVa 10635】Prince and Princess

题目传送门:https://uva.onlinejudge.org/index.php&problem=1576
中文题面:《算法竞赛·入门经典·训练指南》P66

这题真的是好妙啊!
wv6v0iqq6vgq9xxczbs2c

首先O(n^4)的DP大家都会吧?
来说一说O(n*log(n))的做法:
将A串重新编号为1、2、3、4、5····
然后将编码的对应关系应用到B上面去
这样的话,就变成了求B的LIS了
于是搞一个BIT什么的就可以辣!

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

const int N = 250+9;
const int M = N * N;

int n,m,q,p,A[M],B[M],trans[M],vout[M];

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 Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define lowbit(x) ((x)&-(x))
	int MX[M];
	
	inline void modify(int pos, int val) {
		for (int i=pos;i<=m;i+=lowbit(i)) 
			MX[i] = max(MX[i], val);
	}
	
	inline int query(int pos) {
		int ret = 0;
		for (int i=pos;i;i-=lowbit(i)) 
			ret = max(ret, MX[i]);
		return ret;
	}
};

int main(){
	for (int k=1,T=read();k<=T;k++) {
		n = read(); m = n * n + 1;
		p = read() + 1; q = read() + 1;
		for (int i=1;i<=p;i++) A[i] = read();
		for (int i=1;i<=q;i++) B[i] = read();
		
		memset(trans,0,sizeof(trans));
		memset(vout,0,sizeof(vout));
		memset(BIT::MX,0,sizeof(BIT::MX));
		for (int i=1;i<=p;i++) trans[A[i]] = i;
		for (int i=1;i<=q;i++) B[i] = trans[B[i]];
		for (int i=1;i<=q;i++) if (B[i]) {
			vout[i] = BIT::query(B[i]) + 1;
			BIT::modify(B[i],vout[i]);
		}
		
		int ret = 0;
		for (int i=1;i<=q;i++) 
			ret = max(ret, vout[i]);
		printf("Case %d: %d\n",k,ret);
	} 
	return 0;
}

【NOIP十连测】[D3T1] 平均数

题目传送门:https://oi.qizy.tech/wp-content/uploads/2016/10/test3_problem.pdf
官方题解:https://oi.qizy.tech/wp-content/uploads/2016/10/solution.pdf

这题被挖出是大原题了:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1711
另外™鬼畜出题人硬生生把NOIP搞成NOI Professional有意思吗?
YLUL)A7V{OMTL8]~RL2VL$8

std也是二分,然后搞归并排序
不过我有一种更自然的方法,复杂度一样,常数较大:
首先求出前缀和,记为ai
二分最后的答案记为x
不难发现,平均值大于x的需要满足一下条件:\(\frac{{{a_i} – {a_j}}}{{i – j}} \le x\)
然后化简一下得到:\({a_i} – x \cdot i \le {a_j} – x \cdot j\)
换一句话来说,把ai-x*i作为新序列求逆序对的个数就好啦!
结果被卡常了…..
管他的,51nod上能过

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

const int N = 100000+9;
const double EPS = 0.00001;

LL arr[N],k;
double tmp[N];
int n,Rank[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 Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define lowbit(x) ((x)&-(x))
	int cnt[N],tot,lim;
	
	inline void init(int w){
		memset(cnt,0,sizeof(cnt));
		tot = 1; lim = n+1; 
		for (int i=w;i<=lim;i+=lowbit(i)) {
			cnt[i]++;
		}
	}
	
	inline int query(int sta) {
		int ret = 0;
		for (int i=sta;i;i-=lowbit(i)) {
			ret += cnt[i];
		}
		return tot - ret;
	}
	
	inline void insert(int w) {
		tot++;
		for (int i=w;i<=lim;i+=lowbit(i)) {
			cnt[i]++;
		}
	}
};

bool judge(double sta) {
	for (register int i=1;i<=n;++i) {
		tmp[i] = arr[i] - sta*i;
	}
	tmp[n+1] = 0;
	sort(tmp+1,tmp+1+n+1);
	for (register int i=0;i<=n;++i) {
		Rank[i] = lower_bound(tmp+1,tmp+1+n+1,arr[i]-sta*i) - tmp;
	} 
	LL ret = 0;
	BIT::init(Rank[0]);
	for (int i=1;i<=n;i++) {
		ret += BIT::query(Rank[i]);
		BIT::insert(Rank[i]);
	}
	return ret >= k;
}

int main(){
	n = read(); cin>>k;
	k = (LL)n*(n+1) / 2 - k + 1;
	for (int i=1;i<=n;i++) {
		arr[i] = arr[i-1] + read();
	}
	double L = 0, R = 1e9, mid;
	while (R - L > EPS) {
		mid = (L + R) / 2;
		if (judge(mid)) {
			R = mid;
		} else {
			L = mid;
		}
	}
	printf("%.4lf",(R+L)/2);
	return 0;
}

【BZOJ 4627】[BeiJing2016] 回转寿司

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

这个玩意儿,就是一个权值BIT
搞出前缀和之后,得到可行解是一个区间,于是BIT维护一下
考试的时候,一直想着NOI的超级钢琴,搞得连二分都想到了,却没想到正解
考试的时候,态度还是不端正啊H[O(5H1_XNFSSZ~@I6[~$VL

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

const int N = 300000+9;

int arr[N],n,T,ls[N],rs[N];
LL sum[N],L,R,vout,hash[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 Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define lowbit(x) ((x)&-(x))
	int val[N];
	
	inline void modify(int p) {
		for (int i=p;i<=T;i+=lowbit(i))
			val[i]++;
	} 
	
	inline int query(int l, int r) {
		int ret = 0;
		for (int i=r;i;i-=lowbit(i)) ret += val[i];
		for (int i=l-1;i;i-=lowbit(i)) ret -= val[i];
		return ret;
	}	
};

int main(){
	n = read(); L = read(); R = read();
	for (int i=1;i<=n;i++) sum[i] = sum[i-1] + (arr[i]=read()); hash[++T] = 0;
	for (int i=1;i<=n;i++) hash[++T] = sum[i], hash[++T] = sum[i] - R, hash[++T] = sum[i] - L;
	sort(hash+1,hash+1+T); T = unique(hash+1,hash+1+T) - hash - 1;
	for (int i=1;i<=n;i++) 
		ls[i] = lower_bound(hash+1,hash+1+T,sum[i]-R) - hash,
		rs[i] = lower_bound(hash+1,hash+1+T,sum[i]-L) - hash,
		sum[i] = lower_bound(hash+1,hash+1+T,sum[i]) - hash;
	BIT::modify(lower_bound(hash+1,hash+1+T,0)-hash);
	for (int i=1;i<=n;i++) 
		vout += BIT::query(ls[i],rs[i]),
		BIT::modify(sum[i]);
	cout<<vout;
	return 0;
}

【BZOJ 2738】矩阵乘法

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

这个题,真的是妙啊!
整体二分看起来很好用的样子!

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

const int N = 500+9;
const int M = 250000+9;
const int Q = 60000+9;

struct Point{int val,x,y;inline bool operator < (const Point &B) const {return val < B.val;}}p[M];
struct Query{int k,x1,x2,y1,y2,id;}q[Q],buf[Q];

int n,m,vout[Q];

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 Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define lowbit(x) ((x)&-(x))
	int sum[N][N];
	
	inline void modify(int x, int y, int delta) {
		if (x <= 0 || y <= 0) return;
		for (int j=y;j<=n;j+=lowbit(j)) for (int i=x;i<=n;i+=lowbit(i))
			sum[i][j] += delta;
	}
	
	inline int query(int x, int y){
		if (x <= 0 || y <= 0) return 0;
		int ret = 0;
		for (int j=y;j;j-=lowbit(j)) for (int i=x;i;i-=lowbit(i))
			ret += sum[i][j];
		return ret;
	}
};

void solve(int l, int r, int L, int R) {
	if (l == r) for (int i=L;i<=R;i++) vout[q[i].id] = p[l].val;
	else {
		int mid = l + r + 1 >> 1,ls=L-1,rs=R+1;
		for (int i=l;i<=mid-1;i++) BIT::modify(p[i].x,p[i].y,1);
		for (int i=L,tmp;i<=R;i++) {
			tmp = BIT::query(q[i].x1-1,q[i].y1-1);
			tmp += BIT::query(q[i].x2,q[i].y2);
			tmp -= BIT::query(q[i].x1-1,q[i].y2);
			tmp -= BIT::query(q[i].x2,q[i].y1-1);
			if (tmp >= q[i].k) buf[++ls] = q[i];
			else q[i].k -= tmp, buf[--rs] = q[i];
		}
		memcpy(q+L,buf+L,sizeof(buf[0])*(R-L+1));
		for (int i=l;i<=mid-1;i++) BIT::modify(p[i].x,p[i].y,-1);
		if (L <= ls) solve(l,mid-1,L,ls);
		if (rs <= R) solve(mid,r,rs,R);
	}
} 

int main(){
	n = read(); m = read();
	for (int j=1,t=1;j<=n;j++) for (int i=1;i<=n;i++,t++) 
		p[t].x = i, p[t].y = j, p[t].val = read();
	for (int i=1,a,b,c,d,e,f;i<=m;i++) 
 		q[i].y1 = read(), q[i].x1 = read(),
		q[i].y2 = read(), q[i].x2 = read(),
		q[i].k = read(), q[i].id = i;
	sort(p+1,p+1+n*n);
	solve(1,n*n,1,m);
	for (int i=1;i<=m;i++) printf("%d\n",vout[i]);
	return 0;
}

【Codeforces 703D】Mishka and Interesting sum

题目传送门:http://codeforces.com/contest/703/problem/D
中文题面:http://www.cnblogs.com/zqy123/p/5746481.html

这题,第一眼看到就感觉是莫队
然后算一算复杂度感觉能卡过,于是死坑莫队,遂卒
然后看题解,突然想起来以前做过这么一道题,还有分块的解法
不过最简单的做法,可以记录pre[],然后维护区间的unique之后的值
离线的话,一维BIT即可,不离线的话,可以上函数式线段树

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<map>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 1000000+9;

int arr[N],n,m,sum[N],vout[N];
struct Query{
	int l,r,num;
	inline bool operator < (const Query &B) const {
		return r < B.r;
	}
}q[N];
map<int,int> pre;

namespace Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define lowbit(x) ((x)&-(x))
	int v[N];
	
	inline void modify(int i) {
		int tmp = pre[arr[i]]; pre[arr[i]] = i;
		if (tmp) for (int j=tmp;j<=n;j+=lowbit(j)) v[j] ^= arr[i]; 
		for (int j=i;j<=n;j+=lowbit(j)) v[j] ^= arr[i];
	}
	
	inline int query(int l, int r) {
		int ret = 0; l--;
		for (;r;r-=lowbit(r)) ret ^= v[r];
		for (;l;l-=lowbit(l)) ret ^= v[l];
		return ret;
	}
};

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(); for (int i=1;i<=n;i++) arr[i] = read(); 
	m = read(); for (int i=1;i<=m;i++) q[i].l=read(), q[i].r=read(), q[i].num = i;
	sort(q+1,q+1+m); 
	for (int i=1,cur=1;i<=n;i++) {
		sum[i] = sum[i-1] ^ arr[i]; BIT::modify(i);
		for (;cur <= m && q[cur].r == i;cur++) 
			vout[q[cur].num] = sum[i]^sum[q[cur].l-1]^BIT::query(q[cur].l,q[cur].r);
	}
	for (int i=1;i<=m;i++) printf("%d\n",vout[i]);
	return 0;
}

把BZOJ上那题翻出来了,分块的做法让我们召唤黄学长:http://hzwer.com/3663.html