CF1843E Tracking Segments
VP 的时候本来摆烂了，结果快结束的时候想到了做法（没时间敲了 qwq）。这里提供一种和已有题解不同的思路。
我们发现，对于每个修改，我们可以将该点的值修改为这次修改的时间，未修改的点则赋为 \(n+1\)。这样转化后，区间合法的条件就是区间内小于 \(n+1\) 的值至少要有 $\lfloor \frac{r-l+1}{2} \rfloor+1 $ 个，我们令 \(k = \lfloor \frac{r-l+1}{2} \rfloor+1\)，，则最早达到合法条件的时间就是这些值中第 \(k\) 小的。这样一来，我们就可以把问题转化为静态区间第 \(k\) 小，主席树做就行。答案就是所有查询结果中最小值，如果都为 \(n+1\) 则说明无解。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+100;
int n, m;
int root[N], a[N];
int ls[30*N], sum[30*N], rs[30*N],tot;
int read() {
int x = 0, f = 1;
char ch = getchar();
while(ch<'0'||ch>'9') {
if(ch == '-')f = -1;
ch = getchar();
}
while(ch>='0'&&ch<='9') {
x = x*10+ch-48;
ch = getchar();
}
return x*f;
}
void change(int &tr, int lst, int l, int r, int p) {
tr = ++tot;
sum[tr] = sum[lst]+1;
if(l == r) return;
int mid = (l+r)>>1;
ls[tr] = ls[lst], rs[tr] = rs[lst];
if(p <= mid) change(ls[tr], ls[lst], l, mid, p);
else change(rs[tr], rs[lst], mid+1, r, p);
}
int query(int tr, int lst, int l, int r, int kth) {
if(l == r) return l;
int mid = (l+r)>>1;
int tmp = sum[ls[tr]]-sum[ls[lst]];
if(tmp>=kth) return query(ls[tr], ls[lst], l, mid, kth);
else return query(rs[tr], rs[lst], mid+1, r, kth-tmp);
}
int T;
struct question{
int l, r;
}q[N];
int main() {
T = read() ;
while(T--){
n = read(), m = read();
for(int i = 1; i<=m; ++i){
q[i].l = read();
q[i].r = read();
}
int Q = read();
for(int i = 1; i<=n; ++i) a[i] = n+1;
for(int i = 1; i<=Q; ++i){
int tmp = read();
a[tmp] = i;
}
for(int i = 1; i<=n; i++) change(root[i], root[i-1], 1, n+1, a[i]);
int ans = n+1;
for(int i = 1; i<=m; i++) {
int kth = (q[i].r-q[i].l+1)/2+1;
int tmp = query(root[q[i].r], root[q[i].l-1], 1, n+1, kth);
if(tmp == n+1) continue;
else ans = min(ans, tmp);
}
if(ans == n+1) puts("-1");
else printf("%d\n", ans);
for(int i = 1; i<=tot; ++i){//手动清空防止TLE
ls[i] = rs[i] = sum[i] = 0;
}
for(int i = 1; i<=n; ++i) root[i] = 0;
tot = 0;
}
return 0;
}