多省省选联考全真模拟考试2
http://csp.ac/contest/10
T1
带插入可离线区间mex(亵渎)?
首先可以离线把这个插入变成一个修改操作,然后变成带修区间mex
这个可以整体二分,考虑一个询问怎么二分,因为如果1~mid的数都出现的话那么这个询问后面所有位置上的数的前驱一定在大于l的位置才能是保证这个查询的答案能在
然后这个可以预处理一个pre数组,就是记录相同的值前一个位置在哪里
然后这个查询就是r后面一直到n所有的在位置上的值的pre都在l前面,相当于这个最小的pre要在l前面的则一定在前面
你发现这个pre数组可以用线段树维护区间查询,同时用不同的set维护每个值的前驱后继
最后把这个过程放到整体二分上qwq
T2
唯一切掉的题qaq
这么搞?dag还要求能到所有的点?bitset压一下吧?但是就好像要MLE
所以我们可以分个块啥的来浪费时间换空间?
哎?我们这个一二操作好像不错,很适合时间分块啊
但是时间分块怎么重构啊?不太能同时兼容这个min和重构啊
所以稍微转化一下,变成最近的赋值到现在所有的min取min
然后修改分块后询问分三种:(注意下文我们是从最后一个块到之前的块)
- 如果出现时间小于修改块内右端点,就考虑他是不是在块内呢,然后如果在块内我们就意味着这是最后一个还可能对他造成影响的区间了,那么就可以把这部分的min算给他,之后把这个位置换到后面弃掉
否则就是在块前面,我们还盘不到他,之后时间提前之后再盘他
- 否则如果他在之后而且他的查询有赋值操作
那么我们就把当前赋值当做最后一次赋值来算,然后把min的贡献一并算一下,之后把这个操作放后面之后处理
- 否则就是一个随便去个min的操作然后跳到下个
这样就做完啦!
T3
有点难搞
好像是每个点上存一个生成函数,然后直接乘一个多项式或者除一个多项式qwq不太会啊qaq
code(只有T2)
T2
//废了
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define CT const int&
using std::bitset;
using std::swap;
using std::min;
const int MAXN = 1e5 + 7;
const int SIZ = 333;
namespace fastIO {
#define BUF_SIZE (1<<19)
static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
inline char nc() {
if(p1 == pend) {
p1 = buf;
pend = buf + fread(buf, 1, BUF_SIZE, stdin);
}
return *p1++;
}
inline int read() {
int x = 0, f = 1;
char s = nc();
for(; !isdigit(s); s = nc())if(s == '-')f = -1;
for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
return x * f;
}
}
using namespace fastIO;
int n, m, Q, ccnt;
bitset<SIZ> bs[MAXN];//...
int home[MAXN], nxt[MAXN * 3], to[MAXN * 3], minx[MAXN];
int in[MAXN], top[MAXN], vis[MAXN], ans[MAXN];
struct ask {
int opt, u, x, i;
} qry[MAXN], mdf[MAXN];
inline void ct(CT x, CT y) {
ccnt++;
nxt[ccnt] = home[x];
home[x] = ccnt;
to[ccnt] = y;
in[y]++;
}
inline void tpsort() {
static int que[MAXN];
int R = 0, tp = 0;
for(int i = 1; i <= n; ++i) {
if(!in[i]) {
que[++R] = i;
}
}
while(R) {
int u = que[R];
top[++tp] = u;
--R;
for(int i = home[u], v; i; i = nxt[i]) {
v = to[i];
if(--in[v] == 0) {
que[++R] = v;
}
}
}
return ;
}
inline void init(int l, int r) {
for(int i = n; i; --i)bs[i].reset();//块内暴力处理连通性
for(int x = l; x <= r; ++x)
bs[mdf[x].u][x - l] = 1;
for(int k = 1; k <= n; ++k) {
int u = top[k];
for(int i = home[u]; i; i = nxt[i]) {
int v = to[i];
bs[v] |= bs[u];//这里应该手写bitset的
}
}
// for(int i = 1; i <= n; ++i) {
// printf("%d\n", top[i]);
// for(int j = 0; j <= r - l; ++j) {
// if(bs[top[i]][j])printf("%d ", j + l);
// }
// puts("qwq");
// }
return ;
}
inline void fuzhi(int l, int r) {
// printf("%d %d\n", l, r);
memset(vis, 0, sizeof(vis));
for(int i = l; i <= r; ++i) {
if(mdf[i].opt == 1) {
vis[mdf[i].u] = 1;
// printf("%d?\n", mdf[i].u);
}
}
for(int k = 1; k <= n; ++k) {
int u = top[k];
if(vis[u]) {
for(int i = home[u]; i; i = nxt[i]) {
int v = to[i];
vis[v] = 1;
}
}
}
// for(int i = 1; i <= n; ++i)if(vis[i])printf("%dqwq ", i);
//不能直接翻bitset!
}
inline void qumin(int l, int r) {
memset(minx, 0x3f3f3f3f, sizeof(minx));
for(int i = l; i <= r; ++i) {
if(mdf[i].opt == 2)
minx[mdf[i].u] = min(minx[mdf[i].u], mdf[i].x);
}
for(int k = 1; k <= n; ++k) {
int u = top[k];
for(int i = home[u]; i; i = nxt[i]) {
int v = to[i];
minx[v] = min(minx[v], minx[u]);
}
}
// for(int i = 1; i <= n; ++i)printf("%d ", minx[i]);
// puts("QWQ");
}
int ql, ml;
inline void solve(int L, int R) {
init(L, R);
fuzhi(L, R);
qumin(L, R);
int id = ql;
for(; id && qry[id - 1].i > mdf[L].i; --id); //提取
// printf("%d\n", id);
while(id < ql) {
// if(qry[id].i == 15)puts("QWQ");
if(qry[id].i < mdf[R].i) {
// puts("!");
int tmp = R;
for(; mdf[tmp].i > qry[id].i; --tmp);
//回
// printf("%d!!!\n", tmp);
for(; tmp >= L; --tmp) {
if(bs[qry[id].u][tmp - L]) {
ans[qry[id].i] = min(ans[qry[id].i], mdf[tmp].x);
// if(qry[id].i == 15)printf("%d\n", ans[15]);
//2
if(mdf[tmp].opt == 1) {
swap(qry[id], qry[--ql]);
// printf("%d %d %d %d\n", id, ql, qry[id].i, qry[id].u);
//重来
break;
}
}
}
// printf("%d %d\n", tmp, L);
id += tmp < L;
// printf("%d %d\n", id, ql);
} else if(vis[qry[id].u]) {//已经有赋值
// puts("?");
int tmp = R;
for(; mdf[tmp].opt == 2 || !bs[qry[id].u][tmp - L]; --tmp)
if(mdf[tmp].opt == 2 && bs[qry[id].u][tmp - L]) {
ans[qry[id].i] = min(ans[qry[id].i], mdf[tmp].x);//取min
// printf("%d^", ans[ qry[id].i]);
}
ans[qry[id].i] = min(ans[qry[id].i], mdf[tmp].x);
swap(qry[id], qry[--ql]);
// printf("%d %d %d %d\n", id, ql, qry[id].i, qry[id].u);
} else {
// puts("O");
ans[qry[id].i] = min(ans[qry[id].i], minx[qry[id].u]);
++id;
}
// printf("%d %d\n", id, ql);
}
//艹,全是锅
}
int main() {
// freopen("test.in", "r", stdin);
// freopen("T2.out", "w", stdout);
n = read();
m = read();
Q = read();
memset(ans, 0x3f3f3f3f, sizeof(ans));
for(int i = 1, x, y; i <= m; ++i) {
x = read();
y = read();
ct(x, y);
}
tpsort();
ql = 0, ml = 0;
for(int i = 1; i <= Q; ++i) {
mdf[ml].opt = read();
if(mdf[ml].opt <= 2) {//修改
mdf[ml].u = read();
mdf[ml].x = read();
mdf[ml++].i = i;
} else {
qry[ql].u = read();
qry[ql++].i = i;
}
}
ml--;
int L = ml - ml % SIZ, R = ml;
while(L >= 0) {
solve(L, R);
R = L - 1;
L -= SIZ;
}
// printf("%d?\n", ql);
while(ql--)ans[qry[ql].i] = 0;
for(int i = 1; i <= Q; ++i) {
// printf("%d %d?\n", i, ans[i]);
if(ans[i] <= 1e9)
printf("%d\n", ans[i]);
}
return 0;
}