前言

唔，这是我 2023 年第四次担任出题人，我之前还在说我暑假之前差不多就出三套题目（当时心里想的是难题的话我出三套也就差不多了），事实上出题次数大于我的预期。

本场比赛难度难于普及，简单于提高，按照 FJ 要求有一个送分题，其余题目考察范围均在四中当前已经学习的算法范围之内。

T1 翻转（nega）

难度：入门

这个题纯属送分题，首先我们分析一下这个函数的性质，这个函数是当我们输入偶数时返回奇数，输入奇数时返回偶数的一个函数，显然做偶数次翻转和原序列相同，做奇数次翻转得到的结果是原序列翻转一次的序列，然后对应做一次就得。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int x;
    cin >> x;
    string seq;
    cin >> seq;
    if (~x & 1) {
        for (auto& it : seq) {
            it = it == '0' ? '1' : '0';
        }
    }
    cout << seq << endl;
    return 0;
}

T2 老刘的队伍（seq）

板子题，跑出滑动窗口最大值最小值减一减就得。

#include <bits/stdc++.h>

using namespace std;

deque<pair<int, int>> maxQ; // value,pos
deque<pair<int, int>> minQ;
int a[5000001];
vector<int> minans;
vector<int> maxans;

int main()
{
    int k, n;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        if (!maxQ.empty() && i - maxQ.front().second >= k) {
            maxQ.pop_front();
        }
        if (!minQ.empty() && i - minQ.front().second >= k) {
            minQ.pop_front();
        }
        while (!maxQ.empty() && a[i] > maxQ.back().first) {
            maxQ.pop_back();
        }
        while (!minQ.empty() && a[i] < minQ.back().first) {
            minQ.pop_back();
        }
        maxQ.emplace_back(a[i], i);
        minQ.emplace_back(a[i], i);
        if (i >= k) {
            minans.push_back(minQ.front().first);
            maxans.push_back(maxQ.front().first);
        }
    }
    for (int i = 0; i < minans.size(); i++) {
        cout << maxans[i] - minans[i] << ' ';
    }
    cout << endl;
    return 0;
}

T3 跳格子（jump）

改编自 P1516，这道题显然就是要我们解出同余方程$x+km\equiv y+kn(modl)$的解，然后这个式子不是很好解，所以我们应该对他进行若干变换（将模去掉，变成不定方程）：

$$x+km=y+kn+lz(z\in \text{Z})$$$$k(n-m)+lz=x-y$$

我们令$n-m=W$，$x-y=S$，原式就变换成：

$$kW+lz=S$$

由于左边系数$W,l$均为已知，右边$S$也是已知，所以现在就得到了一个关于$k,z$的一个不定方程，我们只要解出$k$的最小值即可。

首先根据 Bezout 定理，如果$S$不为$gcd(W,l)$的倍数的话，方程无解，此时输出Impossible（此处倒是可以骗分，应该给了 20pts）。剩下的就交给 exgcd 去做，注意答案不能为负即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll exgcd(ll a, ll b, ll& x, ll& y)
{
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll r = exgcd(b, a % b, x, y);
    ll tmp = y;
    y = x - (a / b) * y;
    x = tmp;
    return r;
}

int main()
{
    int x, y, m, n, l;
    cin >> x >> y >> m >> n >> l;
    ll a = n - m;
    ll b = l;
    ll c = x - y;
    if (a < 0) {
        a = -a;
        c = -c;
    }
    ll x0 = 0, y0 = 0;
    ll g = exgcd(a, b, x0, y0);
    if (c % g) {
        cout << "Impossible" << endl;
    } else {
        cout << (c / g * x0 % (b / g) + b / g) % (b / g) << endl;
    }
    return 0;
}

T4 价值（value）

又是一个板子题，这个题目显然是要求静态区间第$k$小，可以用的手段是不少的（整体二分，树套树（？），主席树，莫队）。我这里给出整体二分（一种特殊的分治）解决的思路，然后 std 给出 ljt 使用主席树的写法和洛谷日报使用整体二分的写法

整体二分的函数为solve(l,r,L,R)，表示答案在$[l,r]$中，与操作$[L,R]$有关。对于这个问题，我们应该把每个询问都缓存下来放到一个数组里面（典型的变在线为离线的操作，用 tarjan 解 lca 之类的也是类似的办法）。如果原序列的数$\le mid$,那么在树状数组中对应位置$+1$。如果遇到询问操作，那么查询的区间$[ql,qr]$相当于这一个区间中值在$[l,mid]$的个数，如果个数$\le k$，那么答案在$[mid+1,r]$中，那么将$k$减掉左区间长度，把问题放到右区间递归一下就行。如果个数大于$k$，那么就在左区间这样递归下降就可以了。

整体二分代码（来自洛谷日报）：

#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn=200000+10;
const int inf=1e9;
int n,m,a[maxn],c[maxn],ans[maxn],cnt;

struct Query{
	int l,r,k,op,id;
}q[maxn<<1],q1[maxn<<1],q2[maxn<<1];

inline int read(){
	register int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return (f==1)?x:-x;
}
void add(int x,int y){
	for(;x<=n;x+=lowbit(x)) c[x]+=y;
}
int sum(int x){
	int ans=0;
	for(;x;x-=lowbit(x)) ans+=c[x];
	return ans;
}

void solve(int l,int r,int L,int R){
	if(L>R) return ;
	if(l==r){
		for(int i=L;i<=R;i++)
			if(q[i].op==2) ans[q[i].id]=l;
		return ;
	}
	int mid=(l+r)>>1,cnt1=0,cnt2=0,x;
	for(int i=L;i<=R;i++){
		if(q[i].op==1){
			if(q[i].l<=mid) q1[++cnt1]=q[i],add(q[i].id,q[i].r);
			else q2[++cnt2]=q[i];
		}
		else {
			x=sum(q[i].r)-sum(q[i].l-1);
			if(q[i].k<=x) q1[++cnt1]=q[i];
			else q[i].k-=x,q2[++cnt2]=q[i];
		}
	}
	for(int i=1;i<=cnt1;i++)
		if(q1[i].op==1) add(q1[i].id,-q1[i].r);
	for(int i=1;i<=cnt1;i++) q[L+i-1]=q1[i];
	for(int i=1;i<=cnt2;i++) q[L+i+cnt1-1]=q2[i];
	solve(l,mid,L,L+cnt1-1);
	solve(mid+1,r,L+cnt1,R);
}

int main()
{
	n=read(),m=read();
	int l,r,k;
	for(int i=1;i<=n;i++) a[i]=read(),q[++cnt]=(Query){a[i],1,0,1,i};
	for(int i=1;i<=m;i++) l=read(),r=read(),k=read(),q[++cnt]=(Query){l,r,k,2,i};
	solve(-inf,inf,1,cnt);
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

主席树（请自行学习，代码来自 ljt）：

#include <algorithm>
#include <iostream>

using namespace std;
#define ll long long
const ll MAXN = 200010;
const ll MAXMLOGN = 20 * MAXN;
struct Node {
    ll l, r;
    ll lchild, rchild;
    ll val;
};
static Node segt[MAXMLOGN];
static ll tot;
static ll n, m, num;
static ll val[MAXN], f[MAXN];
static ll roots[MAXN];
#define lc segt[cur].lchild
#define rc segt[cur].rchild
void insert(ll v, ll cur, ll pre)
{
    segt[cur].val = segt[pre].val;
    segt[cur].lchild = segt[pre].lchild;
    segt[cur].rchild = segt[pre].rchild;
    if (segt[cur].l == v && segt[cur].r == v) {
        ++segt[cur].val;
        return;
    }
    ll mid = (segt[cur].l + segt[cur].r) / 2;
    if (v <= mid) {
        segt[cur].lchild = ++tot;
        segt[lc].l = segt[cur].l;
        segt[lc].r = mid;
        insert(v, lc, segt[pre].lchild);
    } else {
        segt[cur].rchild = ++tot;
        segt[rc].l = mid + 1;
        segt[rc].r = segt[cur].r;
        insert(v, rc, segt[pre].rchild);
    }
    segt[cur].val = segt[lc].val + segt[rc].val;
}
ostream& operator<<(ostream& os, const Node& rhs)
{
    os << rhs.l << ' ' << rhs.r << ' ' << rhs.val;
    return os;
}
ll query(ll k, ll lcur, ll rcur)
{
    // cout << k << ' ' << segt[lcur] << ' ' << segt[rcur] << endl;
    // _sleep(1000);
    if (segt[lcur].l == segt[lcur].r && segt[rcur].l == segt[rcur].r && segt[rcur].val - segt[lcur].val >= k) {
        return segt[lcur].l == 0 ? segt[rcur].l : segt[lcur].l;
    }
    ll delta = segt[segt[rcur].lchild].val - segt[segt[lcur].lchild].val;
    if (delta >= k) {
        return query(k, segt[lcur].lchild, segt[rcur].lchild);
    } else {
        return query(k - delta, segt[lcur].rchild, segt[rcur].rchild);
    }
}
int main()
{
    ll l, r, k;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
        f[i] = val[i];
    }
    sort(f + 1, f + n + 1);
    num = unique(f + 1, f + n + 1) - f - 1;
    for (int i = 1; i <= n; i++) {
        val[i] = lower_bound(f + 1, f + num + 1, val[i]) - f;
    }
    roots[0] = ++tot;
    segt[roots[0]] = Node { 1, num, 0, 0, 0 };
    for (int i = 1; i <= n; i++) {
        roots[i] = ++tot;
        segt[roots[i]] = segt[roots[i - 1]];
        insert(val[i], roots[i], roots[i - 1]);
    }
    for (int i = 1; i <= m; i++) {
        cin >> l >> r >> k;
        cout << f[query(k, roots[l - 1], roots[r])] << endl;
    }
#ifdef VSCODE
    system("pause");
#endif
    return 0;
}