夏晓光(loveJY)的博客

仍要向下扎根,向上结果

首页 归档 标签 关于 友链

20ZRDay7

2021-03-04 12 min read

A

所有的放在最后提示我们对于每个卡片求出答案

假设Ai<BiA_i<B_i

那么我们对于最后一次在Ai,BiA_i,B_i之间的询问,不管这张卡片之前什么样,操作以后一定是BiB_i朝上

剩余的就是一定会让这个卡片翻折的询问了,直接数点回答即可

数据太水了,我只针对第三档部分分写了正解,然后就拿到了100还是最快的好成绩

//你们这都什么垃圾数据啊
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pb push_back
using namespace std;
const int MAXN = 2e5 + 7;
int n, K, M;
int A[MAXN], B[MAXN], T[MAXN], qwq[MAXN];

inline void solve() {
	ll ans = 0;
	for(int i = 1; i <= n; ++i) {
		int cnt = 0;
		for(int j = K; j >= 0; --j) {
			if(T[j] >= max(A[i], B[i]))cnt++;
			else if(T[j] >= min(A[i], B[i]) || j == 0) {
				if(j != 0)ans += cnt & 1 ? min(A[i], B[i]) : max(B[i], A[i]);
				else ans += cnt & 1 ? B[i] : A[i];
				break;
			}
		}
	}
	printf("%lld\n", ans);
}

struct rec {
	int a, b;
	bool operator<(const rec &x)const {
		return max(a, b) < max(x.a, x.b);
	}
} a[MAXN];
vi v[150];

int rt;
namespace seg {
#define mid ((l+r)>>1)
	int tr[MAXN * 2], T, ls[MAXN * 2], rs[MAXN * 2];
	inline void mdf(int &k, int l, int r, int P, int V) {
		if(!k)k = ++T;
		if(l == r) {
			tr[k] = max(tr[k], V);
			return ;
		}
		if(P <= mid)mdf(ls[k], l, mid, P, V);
		else mdf(rs[k], mid + 1, r, P, V);
		tr[k] = max(tr[ls[k]], tr[rs[k]]);
	}
	inline void mdf2(int &k, int l, int r, int P, int V) {
		if(!k)k = ++T;
		if(l == r) {
			tr[k] = tr[k] + V;
			return ;
		}
		if(P <= mid)mdf2(ls[k], l, mid, P, V);
		else mdf2(rs[k], mid + 1, r, P, V);
		tr[k] = tr[ls[k]] + tr[rs[k]];
	}
	inline int qry2(int k, int l, int r, int L, int R) {
		if(!k)return 0;
		if(L <= l && r <= R)return tr[k];
		if(R <= mid)return qry2(ls[k], l, mid, L, R);
		else if(L > mid)return qry2(rs[k], mid + 1, r, L, R);
		else return qry2(ls[k], l, mid, L, R) + qry2(rs[k], mid + 1, r, L, R);
	}
	inline int qry(int k, int l, int r, int L, int R) {
		if(!k)return 0;
		if(L <= l && r <= R)return tr[k];
		if(R <= mid)return qry(ls[k], l, mid, L, R);
		else if(L > mid)return qry(rs[k], mid + 1, r, L, R);
		else return max(qry(ls[k], l, mid, L, R), qry(rs[k], mid + 1, r, L, R));
	}
	inline void clear() {
		rt = 0;
		T = 0;
		memset(tr, 0, sizeof(tr));
		memset(ls, 0, sizeof(ls));
		memset(rs, 0, sizeof(rs));
	}
}

inline void solve2() {//正解是这部分
	ll ans = 0;
	for(int i = 1; i <= n; ++i)a[i].a = A[i], a[i].b = B[i];
	sort(a + 1, a + n + 1);
	for(int i = 1; i <= K; ++i)v[T[i]].pb(i), seg::mdf(rt, 1, M, T[i], i);
	for(int i = 1; i <= n; ++i)qwq[i] = seg::qry(rt, 1, M, min(a[i].a, a[i].b), max(a[i].a, a[i].b) - 1);
	int j = M + 1;
	seg::clear();
	for(int i = n; i >= 1; --i) {
		for(; j >= max(a[i].a, a[i].b); --j) {
			for(auto u : v[j]) {
				seg::mdf2(rt, 1, K, u, 1);
			}
		}
		int p = seg::qry2(rt, 1, K, qwq[i], K);
		if(qwq[i]) {//有翻折
			ans += p & 1 ? min(a[i].a, a[i].b) : max(a[i].a, a[i].b); //这一次操作之后
		} else {
			ans += p & 1 ? a[i].b : a[i].a;
		}
	}
	printf("%lld\n", ans);
	return ;
}

int main() {
	// freopen("card.in", "r", stdin);
	// freopen("card.out", "w", stdout);
	scanf("%d%d", &n, &K);
	for(int i = 1; i <= n; ++i)
		scanf("%d%d", &A[i], &B[i]), M = max(M, max(A[i], B[i]));
	for(int i = 1; i <= K; ++i)
		scanf("%d", &T[i]), M = max(M, T[i]);
	if(M <= 100)solve2();
	else solve();
	return 0;
}

B

咕掉

C

暴力可以考虑预处理前i个字符的括号匹配消去后的trie,具体就是在trie上走,如果这个字符和上个字符重复就消掉回跳

然后考虑分治,只计算两次修改跨过中间的贡献

相当于一个前缀trie的信息(S1..midS_{1..mid}拼上一个新字符(mid+1再拼上一个后缀trie(Smid+2...RS_{mid+2...R}的信息,然后得到两部分消去串,如果这两个串回文相等就是一个合法的操作

你仔细思考一下,那一个字符可以加在某一个trie上,然后这两个trie合并,就是二分一个长度,然后判断这个长度下是不是相同的,如果是就延长匹配,找到这个最长分界点就不难得到这个消去后的串的哈希了

同理可有反串哈希,然后前面加入后面查询即可

以后写哈希题真的要想想1P\frac{1}{P}会不会卡掉你

//他卡我的1e9+7,998244353/ll
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
const int MAXN = 4e5 + 7;
const ll B = 123;

char s[MAXN];
int a1[MAXN], a2[MAXN], a[MAXN], b1[MAXN];
ull bas[MAXN];
ll ans;
int n, Lx, Rx;
map<ull, int> mp[4][4];

struct rec {
	//需要支持什么呢?
	//诡异的增加字符方式
	//动态哈希值
	//树上单点倍增值(要不然怎么合并啊...)
	int lst, T;
	int ch[MAXN][4], fa[MAXN][19]; //262144
	int bel[MAXN], len[MAXN];
	ull hsh[MAXN], hsh2[MAXN];
	inline void clear() {
		for(int i = 1; i <= T; ++i) {
			for(int j = 0; j <= 18; ++j)fa[i][j] = 0;
			ch[i][3] = ch[i][1] = ch[i][2] = 0;
			hsh[i] = 0;
			hsh2[i] = 0;
			len[i] = 0;
			bel[i] = 0;
		}
		lst = T = 1;//这个清空要命啊/ll
		bel[1] = 0;
	}
	inline void ins(int c) {
		if(bel[lst] == c) {
			lst = fa[lst][0];
			return;//直接回跳!!!
		}
		if(!ch[lst][c]) {
			ch[lst][c] = ++T;
			bel[T] = c;
			fa[T][0] = lst;
			len[T] = len[lst] + 1;
			for(int i = 1; i <= 18; ++i)fa[T][i] = fa[fa[T][i - 1]][i - 1];//蹦跶!
			hsh[T] = (hsh[lst] * B + c);
			hsh2[T] = (hsh2[lst] + c * bas[len[T] - 1]);
		}
		lst = ch[lst][c];
	}
	inline ull qry(int x, int L) {//请保证存在!
		return (hsh[x] - hsh[fa[x][L]] * bas[len[x] - len[fa[x][L]]]);
	}
} t1, t2, t3;

inline ull calc1(int x) {//正串哈希值
	if(x != 1 && x != Rx) {
		t1.lst = a1[x - 1];//暴力!
		t1.ins(a[x]);
		int rc = t1.lst;
		int qc = a2[x + 1];
		for(int j = 18; j >= 0; --j) {
			if(t1.len[rc] < (1 << j) || t2.len[qc] < (1 << j))continue;
			if(t1.qry(rc, j) == t2.qry(qc, j)) { //回跳啊
				rc = t1.fa[rc][j];
				qc = t2.fa[qc][j];
			}
		}
		return (t1.hsh2[rc] + t2.hsh[qc] * bas[t1.len[rc]]);
	} else if(x == Rx && x != 1) {
		t1.lst = a1[x - 1];//暴力!
		t1.ins(a[x]);
		return t1.hsh2[t1.lst];//正
	} else if(x == 1 && x != Rx) {
		t2.lst = a2[x + 1];
		t2.ins(a[x]);
		return t2.hsh[t2.lst];
	} else {
		return a[x];//你以为没有一个字符吗??
	}
}

inline ull calc2(int x) {//反串哈希值
	if(x != n && x != Lx) {
		t3.lst = b1[x + 1];//暴力!
		t3.ins(a[x]);
		int rc = t3.lst;
		int qc = a2[x - 1];
		for(int j = 18; j >= 0; --j) {
			if(t3.len[rc] < (1 << j) || t2.len[qc] < (1 << j))continue;
			if(t3.qry(rc, j) == t2.qry(qc, j)) {//回跳啊
				rc = t3.fa[rc][j];
				qc = t2.fa[qc][j];
			}
		}
		return (t3.hsh2[rc]  + t2.hsh[qc] * bas[t3.len[rc]]);
	} else if(x == Lx && x != n) {
		t3.lst = b1[x + 1];//暴力!
		t3.ins(a[x]);
		return t3.hsh2[t3.lst];//反串的...
	} else if(x == n && x != Lx) {
		t2.lst = a2[x - 1];
		t2.ins(a[x]);
		return t2.hsh[t2.lst];
	} else {
		return a[x];//说不定真没有呢
	}
}

inline void queryinmp(int L, int R) {
	Lx = L;
	Rx = R;
	for(int i = L; i <= R; ++i) {
		int q = a[i];
		for(int j = 1; j <= 2; ++j) {
			a[i] = (q + j) % 3;
			if(a[i] == 0)a[i] = 3;
			ans += mp[a[i]][q][calc2(i)];//反串哈希值
		}
		a[i] = q;
	}
}

inline void pushinmp(int L, int R) {
	Lx = L;
	Rx = R;
	for(int i = L; i <= R; ++i) {
		int q = a[i];//0,1,2?
		for(int j = 1; j <= 2; ++j) {
			a[i] = (q + j) % 3;
			if(a[i] == 0)a[i] = 3;
			mp[q][a[i]][calc1(i)]++;//正串哈希值!
		}
		a[i] = q;
	}
	return;
}

inline void clearmp() {
	for(int i = 1; i <= 3; ++i)for(int j = 1; j <= 3; ++j)mp[i][j].clear();
	return ;
}

inline void solve(int l, int r) {
	if(l == r)
		return;
	int mid = (l + r) >> 1;
	t2.clear();
	for(int i = mid; i >= l; --i)
		t2.ins(a[i]), a2[i] = t2.lst;//a2记录的是后面的
	pushinmp(l, mid); //进入map里面,计算他们的哈希值
	t2.clear();
	for(int i = mid + 1; i <= r; ++i)
		t2.ins(a[i]), a2[i] = t2.lst;
	queryinmp(mid + 1, r);//查询对应的哈希值
	clearmp();
	solve(l, mid);
	solve(mid + 1, r);//所有不跨过mid的..
	return ;
}

inline void init() {
	t1.clear();
	for(int i = 1; i <= n; ++i)
		t1.ins(a[i]), a1[i] = t1.lst;
	t3.clear();
	for(int i = n; i >= 1; --i)t3.ins(a[i]), b1[i] = t3.lst;
}

int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	bas[0] = 1;
	for(int i = 1; i <= n; ++i)bas[i] = bas[i - 1] * B;
	for(int i = 1; i <= n; ++i)a[i] = s[i] - 'a' + 1;
	init();
	solve(1, n);
	printf("%lld\n", ans);
	return 0;
}
Powered by Gridea RSS