好久没打CF了，感觉写代码能力有所下降，vp一场看看，差点被阻击没了。
A
先考虑将某一个数字提出来，可以发现如果这个数字要对答案造成贡献，那么 \(k\) 最小为没有该数字的区间中最长的区间长度加一。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=3e5+10;
vector<int>sum[N];
int n,ans[N];
void solve(){
read(n);
for(int i=1;i<=n;i++){
vector<int>().swap(sum[i]);
ans[i]=n+1;
sum[i].pb(0);
}
for(int i=1,x;i<=n;i++){
read(x);
sum[x].pb(i);
}
for(int i=1;i<=n;i++){
if(sum[i].size()>1){
sum[i].pb(n+1);
int mx=0;
for(int j=0;j<sum[i].size()-1;j++){
mx=max(mx,sum[i][j+1]-sum[i][j]);
}
ans[mx]=min(ans[mx],i);
}
}
write_space(ans[1]==n+1?-1:ans[1]);
for(int i=2;i<=n;i++){
ans[i]=min(ans[i],ans[i-1]);
write_space(ans[i]==n+1?-1:ans[i]);
}
putchar('\n');
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
B
无解很容易判，只需要知道和是不是 \(n\) 的倍数即可。
对于不是无解的，有一个很容易想到的想法，\(1\) 是个很好的中转站，可以将所有数全部放到 \(1\) 上，最后再从 \(1\) 上放回去。
于是我们有了以下策略：
- 将 \(i\) 上的数变为 \(i\) 的倍数
- 将 \(i\) 上的数全部移到 \(1\) 上
- 最后将 \(1\) 上的数平均分配到 \(2\sim n\) 上
现在证明每一步都只需要一次操作。
后面两个操作显然。对于第一个操作，因为 \(p_i\ge 1\)，所以在做 \(i\) 之前，\(1\) 上的数大于等于 \(i-1\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e4+10;
int n,a[N];
void solve(){
read(n);
int sum=0;
for(int i=1;i<=n;i++){
read(a[i]);
sum+=a[i];
}
if(sum%n){
puts("-1");
return;
}
sum/=n;
vector<tuple<int,int,int>>ans;
for(int i=2;i<=n;i++){
ans.pb(make_tuple(1,i,i-1-(a[i]-1)%i));
ans.pb(make_tuple(i,1,(a[i]-1)/i+1));
}
for(int i=2;i<=n;i++){
ans.pb(make_tuple(1,i,sum));
}
write_endl(ans.size());
for(auto x:ans){
write_space(get<0>(x)),write_space(get<1>(x)),write_endl(get<2>(x));
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t;
read(t);
while(t--){
solve();
}
return 0;
}
C
看到异或第一反应 01trie。因为异或对于每一位是独立的，将所有数插入 01trie 后，可以算出 \(x\) 每一位为 \(0/1\) 会带来多少逆序对的贡献。
要算出每一位为 \(0/1\) 会带来的贡献，可以每一个点开一个vector，存储该点子树内的数在原序列中的位置分别为哪些。在树上提一个点出来，它的左右子树分别代表下一位为 \(0/1\) 的数，将两个vector提出来是两个有序序列，同时第二个序列代表的数一定大于第一个序列，\(O(n)\) 扫一遍可以得到 \(x\) 下一位为 \(0\) 的逆序对数，用总对数减去下一位为 \(0\) 的逆序对数即为下一位为 \(1\) 的逆序对数。
因为每个数最多比较 \(\log V\) 次，也最多属于 \(\log V\) 个vector，所以时空复杂度均为 \(O(n\log V)\)，\(V\) 代表值域。
注意：\(10^7\) 个vector空间常数也算挺大的，要稍微卡下空间。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=3e5+10,Lg=30;
int n,a[N],cnt=1;
ll tot[Lg+5][2];
struct node{
int ch[2];
vector<int>num;
}point[N*(Lg+5)];
void ins(int x,int id){
int now=1;
for(int i=Lg;i>=0;i--){
int s=x>>i&1;
if(!point[now].ch[s]){
point[now].ch[s]=++cnt;
}
now=point[now].ch[s];
point[now].num.pb(id);
}
}
void dfs(int now,int p){
int ls=point[now].ch[0],rs=point[now].ch[1];
if(ls){
dfs(ls,p-1);
}
if(rs){
dfs(rs,p-1);
}
if(!ls||!rs){
return;
}
int pos=0;
ll s=0,sum=1ll*point[ls].num.size()*point[rs].num.size();
for(auto x:point[ls].num){
while(pos<point[rs].num.size()&&point[rs].num[pos]<x){
pos++;
}
s+=pos;
}
tot[p][0]+=s;
tot[p][1]+=sum-s;
}
void solve(){
read(n);
for(int i=1;i<=n;i++){
read(a[i]);
ins(a[i],i);
}
dfs(1,Lg);
ll ans=0,sum=0;
for(int i=0;i<=Lg;i++){
if(tot[i][0]<=tot[i][1]){
ans+=tot[i][0];
}
else{
ans+=tot[i][1];
sum+=(1ll<<i);
}
}
write_space(ans),write_endl(sum);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}
D
写完C时间就不怎么够了，D只能算是做的了，一做还做了两个多小时。
看到删边，但没有加边，可以想到将操作反过来，变成加边（不会还有人想写LCT那个时代的眼泪吧）。因为维护的是连通性，所以可以给每次操作赋一个时间，给没删去的边赋上时间 \(inf\)，使用 Kruskal 维护最大生成树，得到每个时刻某个点属于哪个连通块。
但怎么维护某个时刻与某个点连通的点有哪些，线段树合并？显然不是很好。
这时候我们想起了一个被遗忘了很久的东西————Kruskal重构树，我们在求最大生成树时将一条边看作一个新点，从它向原来两棵树的根连边，可以发现在 \(t\) 时刻，与点 \(u\) 连通的点和边均在某个点的子树内，而这个点就是 \(t\) 时刻 \(u\) 所在重构树的根。最后可以通过求dfs序，让操作一变为求某一个区间的最大值，并将其变为 \(0\)，可以用线段树维护。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=4e5+10,Q=5e5+10,M=3e5+10;
int n,m,q,val[N],fa[N],del[N],cnt;
struct edge{
int u,v;
}G[N];
struct query{
int opt,p;
}que[Q];
vector<int>e[N];
int getfa(int x){
if(fa[x]!=x){
fa[x]=getfa(fa[x]);
}
return fa[x];
}
void merge(int u,int v){
u=getfa(u),v=getfa(v);
if(u!=v){
fa[u]=fa[v]=fa[cnt]=++cnt;
e[cnt].pb(u);
e[cnt].pb(v);
}
}
int dfn[N],siz[N],a[N],idx;
void dfs(int u){
dfn[u]=++idx;
a[idx]=val[u];
siz[u]=1;
for(auto v:e[u]){
dfs(v);
siz[u]+=siz[v];
}
}
pii mx[N<<2];
int ls(int p){
return p<<1;
}
int rs(int p){
return p<<1|1;
}
pii qmax(pii x,pii y){
if(x.first==y.first){
if(x.second>y.second){
return x;
}
}
if(x.first>y.first){
return x;
}
return y;
}
void push_up(int p){
mx[p]=qmax(mx[ls(p)],mx[rs(p)]);
}
void build(int p,int l,int r){
if(l==r){
mx[p]=mp(a[l],l);
return;
}
int mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
push_up(p);
}
void update(int p,int l,int r,int pos,int v){
if(l==r){
mx[p]=mp(v,pos);
return;
}
int mid=(l+r)>>1;
if(pos<=mid){
update(ls(p),l,mid,pos,v);
}
else{
update(rs(p),mid+1,r,pos,v);
}
push_up(p);
}
pii query(int p,int l,int r,int q_l,int q_r){
if(q_l<=l&&r<=q_r){
return mx[p];
}
int mid=(l+r)>>1;
pii res;
res=mp(0,0);
if(q_l<=mid){
res=qmax(res,query(ls(p),l,mid,q_l,q_r));
}
if(q_r>mid){
res=qmax(res,query(rs(p),mid+1,r,q_l,q_r));
}
return res;
}
void solve(){
read(n),read(m),read(q);
cnt=n;
for(int i=1;i<=n;i++){
read(val[i]);
}
for(int i=1;i<=m;i++){
read(G[i].u),read(G[i].v);
}
for(int i=1;i<=q;i++){
read(que[i].opt),read(que[i].p);
if(que[i].opt==2){
del[que[i].p]=1;
}
}
for(int i=1;i<=n*2;i++){
fa[i]=i;
}
for(int i=1;i<=m;i++){
if(!del[i]){
merge(G[i].u,G[i].v);
}
}
for(int i=q;i;i--){
if(que[i].opt==2){
merge(G[que[i].p].u,G[que[i].p].v);
}
else{
que[i].p=getfa(que[i].p);
}
}
for(int i=1;i<=cnt;i++){
int x=getfa(i);
if(!dfn[x]){
dfs(x);
}
}
build(1,1,cnt);
for(int i=1;i<=q;i++){
if(que[i].opt==1){
pii ans=query(1,1,cnt,dfn[que[i].p],dfn[que[i].p]+siz[que[i].p]-1);
write_endl(ans.first);
update(1,1,cnt,ans.second,0);
}
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
int t=1;
while(t--){
solve();
}
return 0;
}