T1
\(\sum n\leq 2\times 10^6,x\leq 10^9\)
简单来说，让你在给出的序列中构造差分序列不出现 \(x\) 的一组解。
签到题。
对 \(x\) 分类讨论，排个序，调整一下，注意 \(x=0\) 时 交叉构造以及 \(a_i=0\) 情况即可。
Code
#include<bits/stdc++.h>
#define il inline
#define rint register int
#define ll long long
#define pii pair<int,int>
using namespace std;
const int N=1e5+10,INF=2147483647;
char *p1,*p2,buf[N];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
#define gc() getchar()
il int rd(){
int x=0,f=1;
char ch=gc();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=gc();
return x*f;
}
int n,m;
int a[N],ans[N];
struct dat{
int s,id;
}g[N];
void Main(){
n=rd(),m=rd();
for(int i=1; i<=n; ++i)a[i]=rd();
if(m==0){
sort(a+1,a+1+n,[&](int &a,int &b){return a<b;});
int cnt=0;
for(int i=1; i<=n; ++i){
int now=i;
while(now<n&&a[now]==a[now+1])++now;
g[++cnt].s=now-i+1;g[cnt].id=i;
i=now;
}
sort(g+1,g+1+cnt,[&](dat x,dat y){return a[x.id]<a[y.id];});
bool fl=1;
for(int i=1; i<=cnt; ++i){
if(n-g[i].s<g[i].s-1+(a[g[i].id]==0)){
fl=0;break;
}
}
if(fl){
puts("yes");
priority_queue<pii>q;
for(int i=1; i<=cnt; ++i)q.push({g[i].s,a[g[i].id]});//cout<<a[g[i].id]<<' '<<g[i].s<<endl;
int tot=0;
while(q.size()>=2){
pii x=q.top();q.pop();
pii y=q.top();q.pop();
//printf("%d %d ",x.second,y.second);
if(ans[tot]==x.second)swap(x,y);
ans[++tot]=x.second,ans[++tot]=y.second;
--x.first,--y.first;
if(y.first)q.push(y);
if(x.first)q.push(x);
}
if(!q.empty()){
int x=q.top().second,fl=0;
ans[tot+1]=-INF;
for(int i=0; i<=tot; ++i){
if(i)printf("%d ",ans[i]);
if(ans[i]!=x&&ans[i+1]!=x&&!fl){
printf("%d ",x);
fl=1;
}
}
}else{
for(int i=1; i<=tot; ++i){
printf("%d ",ans[i]);
}
}
puts("");
}else{
puts("no");
}
}
else{
if(m<0)sort(a+1,a+1+n,[&](int a,int b){return a<b;});
else sort(a+1,a+1+n,[&](int a,int b){return a>b;});
int fl=0;
for(int i=2; i<=n; ++i){
if(a[1]-a[i]!=m&&a[i]!=m)fl=i;
}
if(a[1]!=m){
puts("yes");
for(int i=1; i<=n; ++i)printf("%d ",a[i]);
puts("");
}
else if(fl){
puts("yes");
printf("%d ",a[fl]);
for(int i=1; i<=n; ++i)if(i!=fl)printf("%d ",a[i]);
puts("");
}else{
puts("no");
}
}
}
signed main(){
freopen("dif.in","r",stdin);
freopen("dif.out","w",stdout);
int T=rd();
while(T--)Main();
return 0;
}
T2
\(n\leq 10^6\)
啊？一眼淀粉质板子。好，然后你就发现 \(n\log^2 n\) oj 上$ 3s$ 跑不过 \(10^6\)，尊嘟假嘟 o_0？
这题 \(n\log n\)，那没事了。
\(\log^2\) 的：
Code
#include<bits/stdc++.h>
#define il inline
#define rint register int
#define int long long
#define pii pair<int,int>
#define lb(i) (i&-i)
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
using namespace std;
const int N=1e6+10,INF=2147483647,mod=1e9+7;
char *p1,*p2,buf[N];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
#define gc() getchar()
il int rd(){
int x=0,f=1;
char ch=gc();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=gc();
return x*f;
}
int n;
int a[N],ran[N],len;
vector<int>e[N];
int rt,S,siz[N],rt_mx;
bool vis[N];
il void Dfs_rt(int x,int f){
siz[x]=1;
int mx=0;
for(auto y:e[x]){
if(y==f||vis[y])continue;
Dfs_rt(y,x);
siz[x]+=siz[y];
mx=max(mx,siz[y]);
}
mx=max(mx,S-siz[x]);
if(mx<rt_mx)rt_mx=mx,rt=x;
}
vector<pii>P,OP;
il void get_dis(int x,int f,int dep,int val){
P.push_back({dep,lower_bound(ran+1,ran+1+len,val)-ran});
for(auto y:e[x]){
if(y==f||vis[y])continue;
get_dis(y,x,dep+1,max(val,a[y]));
}
}
int sum[N],g[N],ss[N];
il void add(int x,int y,int fl){
for(int i=x; i; i-=lb(i))(sum[i]+=fl*(ran[x]-y)+mod)%=mod;
for(int i=x; i<=len; i+=lb(i))(g[i]+=fl+mod)%=mod,(ss[i]+=fl*y+mod)%=mod;
}
il int query(int x){
int s=0;for(int i=x; i<=len; i+=lb(i))(s+=sum[i])%=mod;
return s;
}
il int query2(int x){
int s=0;for(int i=x; i; i-=lb(i))(s+=g[i])%=mod;return s;
}
il int que(int x){
int s=0;for(int i=x; i; i-=lb(i))(s+=ss[i])%=mod;return s;
}
int ans;
void solve(int x){
// cout<<"RT"<<rt<<endl;
Dfs_rt(rt,0);
vis[x]=1;
int tot=0;
OP.clear();
for(int y:e[x]){
if(vis[y])continue;
P.clear();
get_dis(y,x,1,max(a[y],a[x]));
for(auto t:P){
(ans+=ran[t.second]-t.first+mod)%=mod;
// cout<<ans<<endl;
int s1=query(t.second),s2=query2(t.second-1);//s2:前面<自己 num s1: >= sum
(ans+=s1-(tot-s2+mod)*t.first%mod+mod)%=mod;
// cout<<ans<<endl;
(ans+=s2*(ran[t.second]-t.first+mod)%mod-que(t.second-1)+mod)%=mod;
// cout<<t.first<<' '<<ran[t.second]<<' '<<ans<<' '<<s1<<' '<<s2<<endl;
}
for(auto t:P)
add(t.second,t.first,1),OP.push_back(t);
tot+=P.size();
}
for(auto t:OP)add(t.second,t.first,-1);
for(auto y:e[x]){
if(vis[y])continue;
rt_mx=INF,S=siz[y];
Dfs_rt(y,x);
solve(rt);
}
}
void Main(){
n=rd();
for(int i=1; i<=n; ++i)ran[i]=a[i]=rd();
sort(ran+1,ran+1+n);
len=unique(ran+1,ran+1+n)-ran-1;
for(int u,v,i=1; i<n; ++i){
u=rd(),v=rd();
e[u].push_back(v);
e[v].push_back(u);
}
S=n,rt_mx=INF;
Dfs_rt(1,0);
solve(rt);
cout<<ans*2%mod;
}
signed main(){
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
int T=1;
while(T--)Main();
return 0;
}