Preface
好以后我就是SUA铁粉了，每次打SUA出的题感觉都很好，全程有事情干并且中档题很多很适合我们队这种比上不足的队伍打
不过yysy这场题目偏数据结构和图论方面比较重，而数学方向则不多，刚好撞上了我们队熟悉的地方，因此最后卡着时间过了9题
而且最近CF评测机不知道咋了，这场好多题光读入用scanf就直接TLE飞，换队友写个读优还是TLE，最后没办法把我的fread板子换上去快了十几倍可还行
这两周CCPC秦皇岛和ICPC西安都结束了，感觉这两场的题都有点阴间啊，希望这周CCPC桂林来点阳间出题人的说
A. Live Love
签到题，最长的就是\(m\)，最短的可以二分答案然后贪心check
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
int t,n,m,a[N];
inline bool check(CI x)
{
RI i; int sum=0; for (i=1;i<=n;++i) if (i%(x+1)) ++sum;
return sum>=m;
}
int main()
{
//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
scanf("%d%d",&n,&m); int l=0,r=m,mid,ret;
while (l<=r) if (check(mid=l+r>>1)) ret=mid,r=mid-1; else l=mid+1;
printf("%d %d\n",m,ret);
}
return 0;
}
B. Red Black Tree
本来早就过了这题的，但因为读入问题挂了好久，甚至还去写了一发排序去二分的写法，但后面发现还是fread大法好
这题思路很顺畅，最大值最小一眼考虑二分答案\(lim\)，考虑如何check
对于所有的询问点\(x\)，我们可以先预处理出它们向上最近的红点的距离是多少，如果这个值已经\(\le lim\)了，那么可以直接忽略这个点
而对于剩下的所有点，我们要用一次变色操作去满足所有的点，那么不难发现只能在它们的\(\operatorname{LCA}\)处进行修改
设\(y\)为剩下所有询问点的\(\operatorname{LCA}\)，为了检验染色后是否满足限制，我们设每个点\(x\)到根节点路径的权值和为\(dis_x\)，则要求\(dis_x-dis_y\le lim\)
要求左边的最大值，我们只要求出\(dis_x\)最大的点即可，而求\(\operatorname{LCA}\)可以用欧拉序+RMQ做到\(O(1)\)询问，因此总复杂度是单$\log $的
当然后面还分析了下发现可以将所有点按照向上最近的红点的距离从大到小排序，则可以枚举每次将一段后缀的\(\operatorname{LCA}\)染色并统计答案，不难发现这样和二分的做法是等价的，但常数会小一些
二分的CODE
#include<cstdio>
#include<iostream>
#include<vector>
#include<cctype>
#define int long long
#define RI register int
#define CI const int&
#define Tp template <typename T>
using namespace std;
typedef pair <int,int> pi;
const int N=200005,INF=1e18;
int t,n,m,q,isred[N],dis[N],midis[N],x,y,z; vector <pi> v[N]; vector <int> pnt;
class FileInputOutput
{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
#define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=Fout)++=ch))
char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[30];
public:
inline FileInputOutput(void) { Ftop=Fout; Fend=Fout+S; }
Tp inline void read(T& x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
}
Tp inline void write(T x)
{
RI ptop=0; while (pt[++ptop]=x%10,x/=10);
while (ptop) pc(pt[ptop--]+48); pc('\n');
}
inline void flush(void)
{
fwrite(Fout,1,Ftop-Fout,stdout);
}
#undef tc
#undef pc
}F;
namespace LCA_Solver
{
int seq[N],fir[N],idx,dep[N],Log[N],f[N][20];
inline void DFS(CI now=1,CI fa=0,int mi=INF)
{
seq[fir[now]=++idx]=now; dep[now]=dep[fa]+1; if (isred[now]) mi=0; midis[now]=mi;
for (auto [to,w]:v[now]) if (to!=fa) dis[to]=dis[now]+w,DFS(to,now,mi+w),seq[++idx]=now;
}
inline int mindep(CI x,CI y)
{
return dep[x]<dep[y]?x:y;
}
inline void init(CI n)
{
RI i,j; for (Log[0]=-1,i=1;i<=n;++i) Log[i]=Log[i>>1]+1;
for (i=1;i<=n;++i) f[i][0]=seq[i];
for (j=1;(1<<j)<=n;++j) for (i=1;i+(1<<j)-1<=n;++i)
f[i][j]=mindep(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
inline int getLCA(int x,int y)
{
x=fir[x]; y=fir[y]; if (x>y) swap(x,y);
int k=Log[y-x+1]; return mindep(f[x][k],f[y-(1<<k)+1][k]);
}
}
using namespace LCA_Solver;
inline bool check(CI lim)
{
int lca=-1,mx=-1; for (auto x:pnt)
{
if (midis[x]<=lim) continue;
if (!~lca) { lca=x; mx=dis[x]; continue; }
lca=getLCA(lca,x); mx=max(mx,dis[x]);
}
return mx-dis[lca]<=lim;
}
signed main()
{
//freopen("B.in","r",stdin); freopen("B.out","w",stdout);
for (F.read(t);t;--t)
{
RI i,j; for (F.read(n),F.read(m),F.read(q),i=1;i<=n;++i) v[i].clear(),isred[i]=0;
for (i=1;i<=m;++i) F.read(x),isred[x]=1;
for (i=1;i<n;++i) F.read(x),F.read(y),F.read(z),v[x].push_back(pi(y,z)),v[y].push_back(pi(x,z));
for (idx=0,DFS(),init(2*n-1),i=1;i<=q;++i)
{
F.read(x); pnt.resize(x);
for (j=0;j<x;++j) F.read(pnt[j]);
int l=0,r=1e14,mid,ret; while (l<=r)
if (check(mid=l+r>>1LL)) ret=mid,r=mid-1; else l=mid+1;
F.write(ret);
}
}
return F.flush(),0;
}
排序的CODE
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#define int long long
#define RI register int
#define CI const int&
#define Tp template <typename T>
using namespace std;
typedef pair <int,int> pi;
const int N=200005,INF=1e18;
int t,n,m,q,isred[N],dis[N],midis[N],x,y,z; vector <pi> v[N]; vector <int> pnt;
class FileInputOutput
{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
#define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=Fout)++=ch))
char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[30];
public:
inline FileInputOutput(void) { Ftop=Fout; Fend=Fout+S; }
Tp inline void read(T& x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
}
Tp inline void write(T x)
{
RI ptop=0; while (pt[++ptop]=x%10,x/=10);
while (ptop) pc(pt[ptop--]+48); pc('\n');
}
inline void flush(void)
{
fwrite(Fout,1,Ftop-Fout,stdout);
}
#undef tc
#undef pc
}F;
namespace LCA_Solver
{
int seq[N],fir[N],idx,dep[N],Log[N],f[N][20];
inline void DFS(CI now=1,CI fa=0,int mi=INF)
{
seq[fir[now]=++idx]=now; dep[now]=dep[fa]+1; if (isred[now]) mi=0; midis[now]=mi;
for (auto [to,w]:v[now]) if (to!=fa) dis[to]=dis[now]+w,DFS(to,now,mi+w),seq[++idx]=now;
}
inline int mindep(CI x,CI y)
{
return dep[x]<dep[y]?x:y;
}
inline void init(CI n)
{
RI i,j; for (Log[0]=-1,i=1;i<=n;++i) Log[i]=Log[i>>1]+1;
for (i=1;i<=n;++i) f[i][0]=seq[i];
for (j=1;(1<<j)<=n;++j) for (i=1;i+(1<<j)-1<=n;++i)
f[i][j]=mindep(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
inline int getLCA(int x,int y)
{
x=fir[x]; y=fir[y]; if (x>y) swap(x,y);
int k=Log[y-x+1]; return mindep(f[x][k],f[y-(1<<k)+1][k]);
}
}
using namespace LCA_Solver;
signed main()
{
//freopen("B.in","r",stdin); freopen("B.out","w",stdout);
for (F.read(t);t;--t)
{
RI i,j; for (F.read(n),F.read(m),F.read(q),i=1;i<=n;++i) v[i].clear(),isred[i]=0;
for (i=1;i<=m;++i) F.read(x),isred[x]=1;
for (i=1;i<n;++i) F.read(x),F.read(y),F.read(z),v[x].push_back(pi(y,z)),v[y].push_back(pi(x,z));
for (idx=0,DFS(),init(2*n-1),i=1;i<=q;++i)
{
F.read(x); pnt.resize(x);
for (j=0;j<x;++j) F.read(pnt[j]);
auto cmp=[&](CI x,CI y)
{
return midis[x]<midis[y];
};
sort(pnt.begin(),pnt.end(),cmp);
if (x==1) { F.write(0); continue; }
int ret=midis[pnt[pnt.size()-2]],lca=pnt.back(),mx=dis[pnt.back()];
for (j=pnt.size()-2;j>=0;--j)
mx=max(mx,dis[pnt[j]]),lca=getLCA(lca,pnt[j]),ret=min(ret,max(j!=0?midis[pnt[j-1]]:0LL,mx-dis[lca]));
F.write(ret);
}
}
return F.flush(),0;
}
C. Halting Problem
签到模拟题，徐神写的，我题目都没看
#include <bits/stdc++.h>
using u8 = unsigned char;
using u16 = unsigned short int;
constexpr int $n = 10000 + 5;
int ts[$n][256];
struct {
u8 t, v;
u16 k;
} ops[$n];
int main() {
// freopen("1.in", "r", stdin);
std::ios::sync_with_stdio(false);
int T; std::cin >> T;
for(int ca = 1; ca <= T; ++ca) {
u16 n;
std::cin >> n;
// std::cerr << "n = " << n << char(10);
std::string s;
for(int i = 1; i <= n; ++i) {
u16 tmp;
std::cin >> s >> tmp;
ops[i].v = tmp;
ops[i].t = s[1];
if(s[1] != 'd') std::cin >> ops[i].k;
}
u16 pc = 1;
u8 r = 0;
while(pc != n + 1) {
if(ts[pc][r] == ca) break;
else ts[pc][r] = ca;
auto &[t, v, k] = ops[pc];
switch(t) {
case 'd':
r += v;
pc = pc + 1;
break;
case 'e':
if(r == v) pc = k;
else pc = pc + 1;
break;
case 'n':
if(r != v) pc = k;
else pc = pc + 1;
break;
case 'l':
if(r < v) pc = k;
else pc = pc + 1;
break;
case 'g':
if(r > v) pc = k;
else pc = pc + 1;
break;
default:
return 1;
}
}
std::cout << (pc == n + 1 ? "Yes\n" : "No\n");
}
return 0;
}
D. Pixel Art
又是题目都没看就被徐神秒了的题，好像是利用扫描线维护，并暴力地将矩形合并，可以证明复杂度是对的
#include <bits/stdc++.h>
using llsi = long long signed int;
constexpr int $n = 100050;
//namespace smt {
// constexpr int $node = $n << 2;
// int lb[$node], rb[$node], tt[$node];
// struct Tv { int t, v; };
// std::vector<Tv> vtv[$node];
//
// void build(int p, int l, int r) {
// lb[p] = l, rb[p] = r; vtv[p].clear(); tt[p] = 0;
// if(l == r) return ;
// int lc = p << 1, rc = lc | 1;
// int mid = (l + r) >> 1;
// build(lc, l, mid);
// build(rc, mid + 1, r);
// return ;
// }
//
// void update(int p, int l, int r, int t, int v) {
// if(l > rb[p] || lb[p] > r) return ;
// if(l <= lb[p] && rb[p] <= r) {
// if(tt[p] != t) tt[p] = t, vtv[p].clear();
// tt[p] = t; vv[p] = v; return ;
// }
// int lc = p << 1, rc = lc | 1;
// update(lc, l, r, t, v);
// update(rc, l, r, t, v);
// return ;
// }
//
// template<typename F>
// void get(int p, int l, int r, int t, F callback) {
// if(l > rb[p] || lb[p] > r) return ;
// if(tt[p] == t) callback(vv[p]);
// if(l <= lb[p] && rb[p] <= r) return ;
// int lc = p << 1, rc = lc | 1;
// update(lc, l, r, t, callback);
// update(rc, l, r, t, callback);
// return ;
// }
//} // namespace smt
struct Box { int t, b, l, r; } box[$n];
enum {
TOP = 1,
BOTTOM,
LEFT,
RIGHT,
};
struct Event {
int type;
int l, r;
};
int T, n, m, k, fa[$n], rb[$n], lb[$n];
std::vector<int> ein[$n], eout[$n];
inline int father(int x) {
if(fa[x] == x) return x;
return fa[x] = father(fa[x]);
}
int main() {
// freopen("1.in", "r", stdin);
std::ios::sync_with_stdio(false);
std::cin >> T;
int timeTag = 1;
while(T--) {
std::cin >> n >> m >> k;
for(int i = 1; i <= n; ++i) ein[i].clear(), eout[i].clear();
for(int i = 1; i <= k; ++i) std::cin >> box[i].t >> box[i].l >> box[i].b >> box[i].r;
std::vector<llsi> ans1(n + 2, 0);
std::vector<int> ans2(n + 2, 0);
for(int i = 1; i <= k; ++i) ans1[box[i].t] += box[i].r - box[i].l + 1, ans1[box[i].b + 1] -= box[i].r - box[i].l + 1;
for(int _: {0, 1}) for(int i = 1; i <= n; ++i) ans1[i] += ans1[i - 1];
for(int i = 1; i <= k; ++i) fa[i] = i;
for(int i = 1; i <= k; ++i) {
auto &[t, b, l, r] = box[i];
ein[t].push_back(i);
eout[b].push_back(i);
}
using ti3 = std::tuple<int, int, int>;
std::vector<ti3> ug;
int curAns = 0;
auto try_union = [&] (int a, int b) {
if(!a || !b) return ;
a = father(a); b = father(b);
if(a == b) return ;
curAns -= 1; fa[a] = b;
return ;
};
for(int i = 1; i <= n; ++i) {
ug.clear();
curAns += ein[i].size();
for(int in: ein[i]) {
auto [t, b, l, r] = box[in];
ug.push_back({l, r, in});
lb[l] = in; rb[r] = in;
}
for(int in: ein[i]) {
auto [t, b, l, r] = box[in];
try_union(in, rb[l - 1]);
try_union(in, lb[r + 1]);
}
for(int out: eout[i - 1]) {
auto [t, b, l, r] = box[out];
ug.push_back({l, r, out});
}
std::sort(ug.begin(), ug.end());
int curL = 0, curR = 0, curi = 0;
for(auto [l, r, id]: ug) {
if(l > curR) {
curL = l, curR = r, curi = id;
} else {
curR = std::max(curR, r);
try_union(curi, id);
}
}
for(int out: eout[i]) {
auto [t, b, l, r] = box[out];
lb[l] = 0; rb[r] = 0;
}
ans2[i] = curAns;
}
for(int i = 1; i <= n; ++i) std::cout << ans1[i] << ' ' << ans2[i] << char(10);
}
return 0;
}
E. Infinite Parenthesis Sequence
防AK题，崩撤卖溜
F. Chaleur
图论分类讨论题，感觉祁神很擅长做这一类的题目，上次有个啥三元环四元环的题也是被祁神Rush出来了
首先发现由于给出的图的性质很好，一定可以划分成一个团和一个独立集，因此不妨先求出团的大小
考虑将所有点按照度数从大到小排序，考虑如果团的大小为\(S\)的话，则前\(S\)个点的度数都要\(\ge S-1\)，根据这点我们可以确定团的大小
接下来考虑最大团的方案数，不难发现我们不可能再将团外面的点加入了，因此只能考虑将团外的某个点和团内的点交换
由于团外的点只可能和团内的点有边，因此不难发现若存在一个不在团内的点，它的度数为\(S-1\)，则它一定可以被换进团内，具体方案就是替换掉团中唯一一个和它没有边的点
接下来考虑最大独立集的方案数，这个要复杂一些，首先根据样例一我们发现最大独立集的大小可能是团外部的点数\(+1\)，那么不妨考虑什么时候这个大小可以\(+1\)
因为此时我们要将团中的一个点拿到团外，还要满足这个点和外部的点没有边相连，这就等价于这个点之和团内的点有边，即这个点的度数为\(S-1\)，当存在这种情况时，答案就是团内这样的点的数量
否则不难发现最大独立集的大小就是外部的点的个数，考虑能否将团内一个点和外面的点进行交换
稍作观察会发现当团中存在度数为\(S\)的点时，我们可以将这个点和它唯一连向的团外的店进行交换，此时答案就是团内这样的点的数量再\(+1\)（因为还可以不换出去）
否则剩下的情况要构成最大独立集只有选外部的所有点这一种方案，直接输出\(1\)即可
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int t, n, m, deg[N];
int id[N];
#define RI register int
#define Tp template <typename T>
class FileInputOutput
{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
#define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=Fout)++=ch))
char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[30];
public:
inline FileInputOutput(void) { Ftop=Fout; Fend=Fout+S; }
Tp inline void read(T& x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
}
Tp inline void write(T x,const char ch='\n')
{
RI ptop=0; while (pt[++ptop]=x%10,x/=10);
while (ptop) pc(pt[ptop--]+48); pc(ch);
}
inline void flush(void)
{
fwrite(Fout,1,Ftop-Fout,stdout);
}
#undef tc
#undef pc
}F;
bool cmp(int a, int b){return deg[a]>deg[b];}
int main(){
//freopen("1.in", "r", stdin);
F.read(t);
while (t--){
memset(deg, 0, (n+1)*sizeof(int));
F.read(n); F.read(m);
for (int i=1; i<=n; ++i) id[i]=i;
for (int i=1; i<=m; ++i){
int a, b;
F.read(a); F.read(b);
deg[a]++; deg[b]++;
}
sort(id+1, id+n+1, cmp);
int S=0;
int cnt1=0, cnt2=0, cnt3=0;
for (int i=1; i<=n; ++i){
if (deg[id[i]]>=i-1) S=i;
}
// printf("S=%d\n", S);
for (int i=1; i<=n; ++i){
if (i<=S){
if (deg[id[i]]==S-1) ++cnt1;
if (deg[id[i]]==S) ++cnt2;
}else{
if (deg[id[i]]==S-1) ++cnt3;
}
}
int ans1=cnt3+1;
int ans2;
if (cnt1>0) ans2=cnt1;
else ans2=cnt2+1;
F.write(ans1,' '); F.write(ans2);
}
return F.flush(),0;
}
G. Couleur
为什么这题比赛时过的比BF都多啊不理解，我们队最后一小时才想到做法，然后我上去生死时速30min码完挂了几发发现又是变量没清空，只能说这种多次询问的题还多测属实难顶
注意到这题有强制在线，因此我们不能离线之后再倒着当作合并区间来做
考虑为什么我们会认为合并区间比分裂区间好做，因为这类问题我们可以把两个子区间的贡献加起来，然后加上两个区间相互影响的部分来得到大的区间的答案，而不需要再遍历整个大区间
那么我们可以反过来用这个思路来优化分裂的问题，定义\(R(l,r)\)为区间\([l,r]\)的逆序对个数，假设我们已经知道了\(R(l,r)\)，现在要在\(x\)处分裂\([l,r]\)
考虑怎么计算子区间的影响复杂度比较小，一个很自然的想法就是类似于启发式合并，我们可以用启发式分裂，每次暴力遍历长度较小的区间来统计影响
具体地，不妨设\([l,x-1]\)的长度小于\([x+1,r]\)，那么我们可以先重新用树状数组遍历\([l,x-1]\)求出\(R(l,x-1)\)，然后枚举\(i\in[l,x]\)，求出\(j\in[x+1,r]\and a_j<a_i\)的数量，然后就可以反推出\(R(x+1,r)\)了
区间在某个范围内的数的数量可以用可持久化的权值线段树，最后再用set维护下未删除的区间，以及用可删除堆维护下所有区间的贡献的最大值即可
总复杂度\(O(n\log^ 2 n)\)
#include<cstdio>
#include<iostream>
#include<set>
#include<cctype>
#define RI register int
#define CI const int&
#define Tp template <typename T>
using namespace std;
const int N=100005;
typedef long long LL;
int t,n,a[N],rt[N],tot;
class FileInputOutput
{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)
#define pc(ch) (Ftop!=Fend?*Ftop++=ch:(fwrite(Fout,1,S,stdout),*(Ftop=Fout)++=ch))
char Fin[S],Fout[S],*A,*B,*Ftop,*Fend; int pt[30];
public:
inline FileInputOutput(void) { Ftop=Fout; Fend=Fout+S; }
Tp inline void read(T& x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));
}
Tp inline void write(T x,const char ch='\n')
{
RI ptop=0; while (pt[++ptop]=x%10,x/=10);
while (ptop) pc(pt[ptop--]+48); pc(ch);
}
inline void flush(void)
{
fwrite(Fout,1,Ftop-Fout,stdout);
}
#undef tc
#undef pc
}F;
class Tree_Array
{
private:
int bit[N];
public:
#define lowbit(x) (x&-x)
inline int get(RI x,int ret=0)
{
for (;x<=n;x+=lowbit(x)) ret+=bit[x]; return ret;
}
inline void add(RI x,CI y)
{
for (;x;x-=lowbit(x)) bit[x]+=y;
}
#undef lowbit
}BIT;
struct ifo
{
int l,r; LL v;
friend inline bool operator < (const ifo& A,const ifo& B)
{
if (A.l!=B.l) return A.l<B.l;
if (A.r!=B.r) return A.r<B.r;
return A.v<B.v;
}
};
class Segment_Tree
{
private:
int ch[N*60][2],sum[N*60];
public:
inline void clear(void)
{
for (RI i=1;i<=tot;++i) ch[i][0]=ch[i][1]=sum[i]=0; tot=0;
}
#define TN CI l=1,CI r=n
#define LS l,mid
#define RS mid+1,r
inline void modify(int& now,CI lst,CI pos,TN)
{
now=++tot; ch[now][0]=ch[lst][0]; ch[now][1]=ch[lst][1];
sum[now]=sum[lst]; ++sum[now]; if (l==r) return; int mid=l+r>>1;
if (pos<=mid) modify(ch[now][0],ch[lst][0],pos,LS); else modify(ch[now][1],ch[lst][1],pos,RS);
}
inline int query(CI x,CI y,CI beg,CI end,TN)
{
if (beg<=l&&r<=end) return sum[y]-sum[x]; int mid=l+r>>1,ret=0;
if (beg<=mid) ret+=query(ch[x][0],ch[y][0],beg,end,LS);
if (end>mid) ret+=query(ch[x][1],ch[y][1],beg,end,RS); return ret;
}
#undef TN
#undef LS
#undef RS
}SEG;
int main()
{
//freopen("G.in","r",stdin); freopen("G.out","w",stdout);
for (F.read(t);t;--t)
{
RI i,j; LL ret=0; for (F.read(n),i=1;i<=n;++i)
F.read(a[i]),ret+=BIT.get(a[i]+1),BIT.add(a[i],1);
for (i=1;i<=n;++i) BIT.add(a[i],-1);
set <ifo> s; multiset <LL> hp;
s.insert((ifo){1,n,ret}); hp.insert(ret);
for (SEG.clear(),i=1;i<=n;++i) SEG.modify(rt[i],rt[i-1],a[i]);
for (i=1;i<=n;++i)
{
LL lstans=*hp.rbegin(); F.write(lstans," \n"[i==n]);
LL x; F.read(x); x^=lstans;
auto it=s.upper_bound((ifo){x,n,(LL)1e18}); --it;
int l=it->l,r=it->r; LL v=it->v;
s.erase(it); hp.erase(hp.find(v));
if (l==r) { hp.insert(0); continue; }
if (x-1-l+1<=r-(x+1)+1)
{
LL cur=0; for (j=l;j<x;++j)
cur+=BIT.get(a[j]+1),BIT.add(a[j],1);
if (l<=x-1) s.insert((ifo){l,x-1,cur}); hp.insert(cur);
for (v-=cur,j=l;j<x;++j) BIT.add(a[j],-1),v-=(a[j]>a[x]);
for (j=l;j<=x;++j) if (1<=a[j]-1) v-=SEG.query(rt[x],rt[r],1,a[j]-1);
s.insert((ifo){x+1,r,v}); hp.insert(v);
} else
{
LL cur=0; for (j=x+1;j<=r;++j)
cur+=BIT.get(a[j]+1),BIT.add(a[j],1);
if (x+1<=r) s.insert((ifo){x+1,r,cur}); hp.insert(cur);
for (v-=cur,j=x+1;j<=r;++j) BIT.add(a[j],-1),v-=(a[j]<a[x]);
for (j=x;j<=r;++j) if (a[j]+1<=n) v-=SEG.query(rt[l-1],rt[x-1],a[j]+1,n);
s.insert((ifo){l,x-1,v}); hp.insert(v);
}
//for (auto [l,r,v]:s) printf("%d %d %d\n",l,r,v); puts("------");
}
}
return F.flush(),0;
}
H. Traveling on the Axis
刚开始没想到关键点一下还没秒掉这个题，后面冷静思考后发现是个签
首先走路花的时间是固定的，可以直接统计不管，因此只要考虑等待时间的计算
假设起点位于\(st\)，我们考虑第\(i\)个信号灯对于当前位置的影响，手玩一下会发现当且仅当\(s_{i-1}=s_i\)时，这个信号灯会对终点\(tar\ge i\)的所有路径产生一秒的等价，因此它的贡献就是\(n-i+1\)
因此用一个后缀和统计下贡献，然后注意下由于起点位置不同带来的它后面的第一个灯的贡献与否的影响即可
#include<cstdio>
#include<iostream>
#include<cstring>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,sfx[N]; char s[N];
signed main()
{
//freopen("H.in","r",stdin); freopen("H.out","w",stdout);
for (scanf("%lld",&t);t;--t)
{
RI i; for (scanf("%s",s+1),n=strlen(s+1),sfx[n+1]=0,i=n;i>1;--i)
sfx[i]=sfx[i+1]+(s[i]==s[i-1]?n-i+1:0); int ans=0;
for (sfx[1]=sfx[2],i=0;i<n;++i)
{
int dlt=sfx[i+1];
if (i==0)
{
if (s[1]=='0') dlt+=n;
} else
{
if (s[i+1]==s[i]) dlt-=n-(i+1)+1;
if (s[i+1]=='0') dlt+=n-(i+1)+1;
}
ans+=(n-i)*(n-i+1)/2LL+dlt;
}
printf("%lld\n",ans);
}
return 0;
}
I. Kuririn MIRACLE
很有意思的几何题，队友手玩了会发现要解微分方程？后面发现没有这题题解，这下只能弃疗了
J. Press the Button
队友想+写的一个数学题？我全程没参与题意都不知道
但祁神把读入的\(t\)和数据组数的\(T\)搞混然后WA了几发实在是太乐了，颇有我之前输出不排序和特判不换行的风范了
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T, a, b, c, d, v, t;
int gcd(int a, int b){
return 0==b ? a : gcd(b, a%b);
}
signed main(){
scanf("%lld", &T);
while (T--){
scanf("%lld%lld%lld%lld%lld%lld", &a, &b, &c, &d, &v, &t);
if (a<=v || c<=v) printf("%lld\n", (t/a+1)*b+(t/c+1)*d-1);
else{
vector<int> vec;
int ans=0;
int lstA=0, lstC=0;
vec.push_back(0);
while (1){
if (lstA==lstC && lstA!=0) break;
if (lstA+a<=lstC+c) lstA+=a, vec.push_back(lstA);
else lstC+=c, vec.push_back(lstC);
}
vec.pop_back();
// for (int x : vec) printf("%lld ", x); puts("");
int tmp=b*(c/gcd(a, c))+d*(a/gcd(a, c));
int left=t%vec.back();
for (int i=1; i<vec.size(); ++i){
if (vec[i]-vec[i-1]>v){
--tmp;
if (vec[i]<=left) --ans;
}
}
// printf("tmp=%lld\n", tmp);
ans += (t/vec.back()) *tmp + b+d-1;
ans += (left/a) * b;
ans += (left/c) * d;
printf("%lld\n", ans);
}
}
return 0;
}
K. XOR Clique
签到题，不难发现一个Clique中的所有数的最高位必须相同，因此用一个桶统计下即可
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,c[50],x;
int main()
{
//freopen("K.in","r",stdin); freopen("K.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; for (scanf("%d",&n),memset(c,0,sizeof(c)),i=1;i<=n;++i)
for (scanf("%d",&x),j=30;j>=0;--j) if ((x>>j)&1) { ++c[j]; break; }
printf("%d\n",*max_element(c,c+31));
}
}
Postscript
应该是桂林站前最后一次VP训练了，希望这段时间的加训付出能有所收获吧
- Qingdao The Universal ACM-ICPC Regionalqingdao the universal acm-icpc the universal acm-icpc regional universal qingdao stage the qingdao programming the universal universal qingdao stage 2018 programming acm-icpc american regional acm-icpc regional contest nanjing acm-icpc regional contest seoul universal stage the 2nd the universal binjiang contest