【日常小测】回转寿司

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/07/20170623_statement.pdf

解题报告

看到这题我们不难想到分块
更进一步,对于每一个块来说,块内的数的相对大小不变
于是我们只需要用堆便可维护块内有哪些数

再稍加观察,我们发现只要再用一个堆记录块内的操作,然后从左向右扫一遍便可更新具体的数
于是我们就可以在:$O(n^{1.5} \log n)$的时间复杂度内解决这个问题了

另外priority_queue的构造函数是$O(n)$的

Code

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

const int N = 400009;
const int M = 25009;
const int S = 1000;
const int B = N / S + 10; 

int n, sn, m, arr[N];
priority_queue<int> val[B];
vector<int> opr[B];

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

inline void get_element(int w) {
	if (opr[w].empty()) {
		return;
	}
	priority_queue<int, vector<int>, greater<int> > heap(opr[w].begin(), opr[w].end()); 
	for (int i = max(1, w * S), lim = min((w + 1) * S - 1, n); i <= lim; i++) {
		if (arr[i] > heap.top()) {
			heap.push(arr[i]);
			arr[i] = heap.top();
			heap.pop();
		}
	}	
	opr[w].clear();
}

inline int modify_element(int w, int s, int t, int v) {
	get_element(w);
	int tmp = -1;
	for (int i = s; i <= t; i++) {
		if (v < arr[i]) {	
			tmp = arr[i];
			swap(v, arr[i]);
		}
	}
	val[w] = priority_queue<int>(arr + max(1, w * S), arr + 1 + min(n, (w + 1) * S - 1));
	return v;
}

inline int modify_block(int w, int v) {
	val[w].push(v);
	int ret = val[w].top();
	val[w].pop();
	if (v != ret) {
		opr[w].push_back(v);
	}
	return ret;
}

inline int solve(int s, int t, int v) {
	int ss = s / S, st = t / S;
	v = modify_element(ss, s, min(t, (ss + 1) * S - 1), v);
	if (ss != st) {
		for (int i = ss + 1; i < st; i++) {
			v = modify_block(i, v);
		}
		v = modify_element(st, st * S, t, v);
	}
	return v;
}

int main() {
	n = read(); m = read();
	sn = n / S;
	for (int i = 1; i <= n; i++) {
		arr[i] = read();
	}
	for (int i = 0; i <= sn; i++) {
		val[i] = priority_queue<int>(arr + max(1, i * S), arr + 1 + min(n, (i + 1) * S - 1));
	}
	for (int tt = 1; tt <= m; tt++) {
		int s = read(), t = read(), v = read();
		if (s <= t) {
			v = solve(s, t, v);		
		} else {
			v = solve(s, n, v);
			v = solve(1, t, v);
		}
		printf("%d\n", v);
	}
	return 0;
}

【日常小测】异或与区间加

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf

解题报告

这题又是一道多算法互补的题目
通过分类处理使复杂度达到$O((n+m)\sqrt{n})$
具体来讲是将以下两个算法结合:

1. 枚举右端点的值,若左端点的合法位置超过$\sqrt{n}$个

考虑每一个左右端点应该加减多少,使用前缀和技巧将复杂度优化到$O(n + m)$
具体细节不想写了,有点麻烦_(:з」∠)_
然后因为合法位置超过了$\sqrt{n}$个,所以这种情况至多出现$\sqrt{n}$个,复杂度符合要求

2. 其他情况

因为左端点不超过$\sqrt{n}$个,所以可以排序之后依次处理
使用分块来维护左端点的值,单次修改是$\sqrt{n}$的,单次查询是$O(1)$的

Code

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

const int N = 150009;
const int MOD = 1073741824;
const int blk_sz = 800;

int n, m, k, a[N];
UI a1[N], ans[N], blk_tag[N], tag[N];
vector<int> num, pos_list[N];
vector<pair<int, int> > left_list[N], right_list[N];
struct Query{
	int l, r, w;
	inline bool operator < (const Query &QQQ) const {
		return r > QQQ.r;
	} 
}q[N];

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

inline int find(int x) {
	int l = 0, r = num.size() - 1, mid;
	while (l <= r) {
		mid = l + r >> 1;
		if (num[mid] == x) {
			return mid;
		} else if (num[mid] < x) {
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	return -1;
}

inline void solve(int A, int B) {
	static UI a2[N], cur;
	memset(a2, 0, sizeof(a2));
	for (int i = 1; i <= n; i++) {
		a2[i] = a2[i - 1] + (a[i] == num[B]);
	}
	cur = 0;
	for (int i = n; i; i--) {
		if (a[i] == num[B]) {
			cur += a1[i];
		}
		if (a[i - 1] == num[A]) {
			ans[i] += cur;
		}
		for (int j = 0; j < (int)left_list[i].size(); ++j) {
			cur -= (UI)left_list[i][j].second * (a2[left_list[i][j].first] - a2[i - 1]);
		}
	}
	memset(a2, 0, sizeof(a2));
	for (int i = 1; i <= n; ++i) {
		a2[i] = a2[i - 1] + (a[i - 1] == num[A]);
	}
	cur = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i - 1] == num[A]) {
			cur -= a1[i];
		}
		if (a[i] == num[B]) {
			ans[i + 1] += cur;
		}
		for (int j = 0; j < (int)right_list[i].size(); ++j) {
			cur += (UI)right_list[i][j].second * (a2[i] - a2[right_list[i][j].first - 1]);
		}
	}
}

int main() {
	freopen("xor.in", "r", stdin);
	freopen("xor.out", "w", stdout);
	n = read(); m = read(); k = read();
	num.push_back(0);
	for (int i = 1; i <= n; ++i) {
		a[i] = a[i - 1] ^ read();
		num.push_back(a[i]);
	}
	sort(num.begin(), num.end());
	num.resize(unique(num.begin(), num.end()) - num.begin());
	for (int i = 0; i <= n; i++) {
		int pp = find(a[i]);
		pos_list[pp].push_back(i);
	}
	for (int i = 1, l, r, w; i <= m; ++i) {
		l = q[i].l = read();
		r = q[i].r = read();
		w = q[i].w = read();	
		left_list[l].push_back(make_pair(r, w));
		right_list[r].push_back(make_pair(l, w));
		a1[l] += w; 
		a1[r + 1] -= w;
	}
	sort(q + 1, q + 1 + m);
	for (int i = 1; i <= n; ++i) {
		a1[i] += a1[i - 1];
	}
	for (int i = 0; i < (int)num.size(); i++) {
		int r = i, l = find(num[i] ^ k);
		if (l != -1 && (int)pos_list[l].size() > blk_sz) {
			solve(l, r);
		}
	}
	for (int r = n, cur = 0; r; r--) {
		while (cur < m && q[cur + 1].r >= r) {
			++cur;
			for (int i = q[cur].l, lim = min(q[cur].r, (q[cur].l / blk_sz + 1) * blk_sz - 1); i <= lim; ++i) {
				tag[i] += q[cur].w;
			}
			for (int i = q[cur].l / blk_sz + 1, lim = q[cur].r / blk_sz - 1; i <= lim; ++i) {
				blk_tag[i] += q[cur].w;
			}
			for (int i = max(q[cur].r / blk_sz, q[cur].l / blk_sz + 1) * blk_sz; i <= q[cur].r; ++i) {
				tag[i] += q[cur].w;
			}
		}
		int t = find(a[r] ^ k);
		if (t != -1 && (int)pos_list[t].size() <= blk_sz) {
			for (int tt = 0; tt < (int)pos_list[t].size(); ++tt) {
				int l = pos_list[t][tt] + 1;
				if (l <= r) {
					ans[l] += tag[l] + blk_tag[l / blk_sz];
					ans[r + 1] -= tag[l] + blk_tag[l / blk_sz];
				} else {
					break;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		ans[i] += ans[i - 1];
		printf("%d ", ans[i] % MOD);
	}
	return 0;
}

【日常小测】友好城市

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf

解题报告

这题的前置知识是把求$SCC$优化到$O(\frac{n^2}{32})$
具体来说,就是使用$bitset$配合$Kosaraju$算法

有了这个技能以后,我们配合$ST$表来实现提取一个区间的边的操作
这样的话,总的时间复杂度是:$O(\frac{(\sqrt{m} \log m + q) n^2}{32}+q \sqrt{m})$

然后我懒,没有用$ST$表,用的莫队,时间复杂度是$O(\frac{(m + q) n^2}{32}+q \sqrt{m})$
调一调块大小,勉勉强强卡过去了

Code

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

const int N = 159;
const int M = 300009;
const int QQ = 50009;
const int BlockSize = 1200;
const UI ALL = (1ll << 32) - 1;

int n, m, q, U[M], V[M], ans[QQ]; 
struct Query{
	int l, r, blk, id;
	inline bool operator < (const Query &Q) const {
		return blk < Q.blk || (blk == Q.blk && r < Q.r);
	}
}qy[QQ];
struct Bitset{
	UI v[5];
	inline void flip(int x) {
		v[x >> 5] ^= 1 << (x & 31);
	}
	inline void set(int x) {
		v[x >> 5] |= 1 << (x & 31);
	}
	inline void reset() {
		memset(v, 0, sizeof(v));
	}
	inline bool operator [](int x) {
		return v[x >> 5] & (1 << (x & 31));
	}
}g[N], rg[N], PreG[M / BlockSize + 9][N], PreRG[M / BlockSize + 9][N];

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

inline void AddEdge(int u, int v, Bitset *a1, Bitset *a2) {
 	a1[u].set(v);
 	a2[v].set(u);
}

class Kosaraju{
	vector<int> que;
	Bitset vis;
public:
	inline int solve() {
		vis.reset();
		que.clear();
		for (int i = 1; i <= n; ++i) {
			if (!vis[i]) {
				dfs0(i);
			}
		}
		vis.reset();
		int ret = 0;
		for (int j = n - 1; ~j; j--) {
			int i = que[j];
			if (!vis[i]) {
				int cnt = dfs1(i);
				ret += cnt * (cnt - 1) / 2;
			}
		}
		return ret;
	}
private:
	inline void dfs0(int w) {
		vis.flip(w);
		for (int i = 0; i < 5; i++) {
			for (UI j = g[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					dfs0(t);
				}
			}
		}
		que.push_back(w);
	}
	inline int dfs1(int w) {
		vis.flip(w);
		int ret = 1;
		for (int i = 0; i < 5; i++) {
			for (UI j = rg[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					ret += dfs1(t);
				}
			}
		}
		return ret;
	}
}scc;

int main() {
	freopen("friend.in", "r", stdin);
	freopen("friend.out", "w", stdout);
	n = read(); m = read(); q = read();
	for (int i = 1; i <= m; i++) {
		U[i] = read();
		V[i] = read();
		AddEdge(U[i], V[i], PreG[i / BlockSize], PreRG[i / BlockSize]);
	}
	for (int i = 1; i <= q; i++) {
		qy[i].l = read(); 
		qy[i].r = read();
		qy[i].blk = qy[i].l / BlockSize;
		qy[i].id = i;
	}
	sort(qy + 1, qy + 1 + q);
	Bitset CurG[N], CurRG[N];
	for (int i = 1, L = 1, R = 0; i <= q; i++) {
		if (qy[i].blk != qy[i - 1].blk || i == 1) {
			L = qy[i].blk + 1;
			R = L - 1;	
			for (int j = 1; j <= n; j++) {
				CurG[j].reset();
				CurRG[j].reset();
			}
		}
		if (qy[i].r / BlockSize - 1 > R) {
			for (int j = R + 1, lim = qy[i].r / BlockSize - 1; j <= lim; j++) {
				for (int k = 1; k <= n; k++) {
					for (int h = 0; h < 5; h++) {
						CurG[k].v[h] ^= PreG[j][k].v[h];
						CurRG[k].v[h] ^= PreRG[j][k].v[h];
					}
				}
			}
			R = qy[i].r / BlockSize - 1;
		}
		if (L <= R) {
			for (int i = 1; i <= n; i++) {
				g[i] = CurG[i];
				rg[i] = CurRG[i];
			}
			for (int l = qy[i].l; l < L * BlockSize; l++) {
				AddEdge(U[l], V[l], g, rg);
			}
			for (int r = (R + 1) * BlockSize; r <= qy[i].r; r++) {
				AddEdge(U[r], V[r], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		} else {
			for (int i = 1; i <= n; i++) {
				g[i].reset();
				rg[i].reset();
			}
			for (int j = qy[i].l; j <= qy[i].r; ++j) {
				AddEdge(U[j], V[j], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		}
	}
	for (int i = 1; i <= q; i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}

【BZOJ 3509】[CodeChef] COUNTARI

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3509
原题传送门:https://www.codechef.com/problems/COUNTARI
神犇题解:http://blog.miskcoo.com/2015/04/bzoj-3509

解题报告

这题如果没有$i<j<k$那么撸一发FFT就可以了
现在考虑$i<j<k$的限制,我们可以分块!

设块的大小为$S$,那么对于$j,k$或$i,j$在同一个块内的,我们可以$O(S^2)$暴力
对于$i,k$都不与$j$在同一个块的情况,我们可以用FFT做到$O(\frac{n}{S} \cdot v \log v)$
然后复杂度分析要准确的话应该搞倒数,但我不会QwQ

XeHoTh似乎用一份巨强暴力,卡到了BZOJ和CC的Rank 1
伏地膜啊!太强大了 _(:з」∠)_

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int M = 70009;
const int N = 100009;
const int T = 15;
const int L = 1 << T + 1;
const double EPS = 0.5;
const double PI = acos(-1);
 
int n,S,ed,arr[N],tot[M],pos[M];
struct COMPLEX{
	double a,b;
	inline COMPLEX() {}
	inline COMPLEX(double x, double y):a(x),b(y) {}
	inline COMPLEX operator - (const COMPLEX &B) {return COMPLEX(a-B.a,b-B.b);}
	inline COMPLEX operator + (const COMPLEX &B) {return COMPLEX(a+B.a,b+B.b);}
	inline COMPLEX operator * (const COMPLEX &B) {return COMPLEX(a*B.a-b*B.b,a*B.b+b*B.a);}
}a1[M],a2[M],bas(1,0);
LL vout,cnt[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;
}
 
inline void FFT(COMPLEX *a, int T = 1) {
    for (int i=0;i<L;i++) if (pos[i]<i) swap(a[pos[i]],a[i]);
    for (int l=2;l<=L;l<<=1) {
        COMPLEX wn(cos(2*PI/l),sin(2*PI/l)*T),w(1,0);
        for (int i=0;i<L;i+=l,w=bas) {
            for (int j=i;j<(i+(l>>1));j++,w=w*wn) {
                COMPLEX tmp = w * a[j+(l>>1)];
                a[j+(l>>1)] = a[j] - tmp;
                a[j] = a[j] + tmp;
            }
        }
    }   
}
 
int main() {
    n = read(); S = 4000;
    for (int i=1;i<=n;i++) arr[i] = read();
    for (int i=1;i<L;i++) pos[i] = (pos[i>>1]>>1)|((i&1)<<T);
    for (int i=S+1;i+S<=n;i+=S) { 
        memset(a1,0,sizeof(a1));
        memset(a2,0,sizeof(a2));
        for (int j=1;j<i;j++) a1[arr[j]] = a1[arr[j]] + bas;
        for (int j=i+S;j<=n;j++) a2[arr[j]] = a2[arr[j]] + bas;
        FFT(a1); FFT(a2);
        for (int j=0;j<L;j++) a1[j] = a1[j] * a2[j];
        FFT(a1, -1);
        for (int j=0;j<L;j++) cnt[j] = a1[j].a / L + EPS;
        for (int j=i;j<i+S;j++) vout += cnt[arr[j]<<1];
    }
    for (int i=1,t;i<=n;i+=S) {
        ed = max(ed, i);
        for (int j=i,lim=min(n+1,i+S);j<lim;j++) {
            for (int k=j+1;k<lim;k++) {
                t = (arr[j] << 1) - arr[k];
                vout += t<M&&t>0? tot[t]: 0;
            }
            tot[arr[j]]++;
        }
    }
    memset(tot,0,sizeof(tot));
    for (int i=ed,t;i>0;i-=S) {
        for (int j=min(n,i+S-1);j>=i;j--) {
            for (int k=j-1;k>=i;k--) {
                t = (arr[j] << 1) - arr[k];
                vout += t<M&&t>0? tot[t]: 0;
            }
        }
        for (int j=min(n,i+S-1);j>=i;j--) tot[arr[j]]++;
    } 
    printf("%lld\n",vout);
    return 0;
}

【BZOJ 4537】[HNOI2016] 最小公倍数

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4537
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/5406018.html
神犇题解Ⅱ:http://blog.csdn.net/heheda_is_an_oier/article/details/51197705

解题报告

考虑只有 ${{\rm{2}}^a}$ 的限制的话
只需要将边和询问排序后依次执行就可以了
具体的话,就是判一判在不在同一个连通块和连通块内的最大值是否符合条件

现在有两个限制,且独立不了的话
那么考虑将 $a$ 分块
边和询问按照 $a$ 所在的块为第一关键字,$b$ 为第二关键字
于是单次询问的加边数量就在 $\sqrt m $ 级别了
于是再搞一个持久化并查集什么的,遇到操作就暴力插入、还原
于是复杂度就是 $O({m^{1.5}}\log n)$ 辣!

【BZOJ 2821】作诗(Poetize)

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2821
神犇题解Ⅰ:http://blog.csdn.net/PoPoQQQ/article/details/40372067
神犇题解Ⅱ:http://www.cnblogs.com/JSZX11556/p/5031198.html

解题报告

这货最开始想用高级数据结构来做
想了半个小时,一点思路都没有 QwQ

好吧,看完题解发现全™写的是分块
不过这题的姿势又有一点不一样

一般的分块是:

大块直接扫一遍,顺便统计答案

这题的分块得预处理块与块之间的关系

$ f[i][j]$ 表示第i个大块到第j个大块的答案

似乎这样的复杂度才是对的
时间复杂度: $ O({n^{1.5}}\log (n))$