A1. Dances (Easy version)
把 \(a,b\) 序列都从小到大排序，\(a\) 贪心删大的，\(b\) 贪心删小的，二分答案并 \(O(n)\) \(\text{check}\)。
Code
```cpp const int N=1e5+5; int T,n,m; int a[N],b[N]; il bool check(int mid) { for(int i=1,j=mid+1;i<=n-mid;i++,j++) if(a[i]>=b[j]) return 0; return 1; } int main() { T=read(); while(T--) { n=read(),m=read(); a[1]=1; for(int i=2;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) b[i]=read(); sort(a+1,a+n+1),sort(b+1,b+n+1); int l=0,r=n; while(l >1; if(check(mid)) r=mid; else l=mid+1; } printf("%d\n",l); } return 0; } ```A2. Dances (Hard Version)
日常给大家提供乐子。
Solution 1
现在的限制变成了 \(m\le 10^9\)，肯定不能一个一个求答案。但是发现我们只关心这个 \(a_1\) 和 \(a,b\) 中其余的每个元素的大小关系。也就是说我们只要枚举 \(4\times 10^5\) 种大小关系，对他们分别求解就可以得到所有答案了。
原来对一个给定序列求答案的时间复杂度是 \(O(n\log n)\)，考虑优化这个过程。
同样二分删掉的数量 \(mid\)，设 \(a_1=x\)，\(a\) 序列排序时不包含 \(a_1\)。
那么把 \(x\) 插进 \(a\) 的对应位置，需要判断的区间可以分成 \(3\) 段：\(a\) 序列中在 \(x\) 前的部分，\(x\) 的位置，\(a\) 序列中在 \(x\) 后的部分。
已经有两个 \(\log\) 了，需要 \(O(1)\) 地判断 \([a_l,a_r]\) 与 \([b_L,b_R]\) 对应起来是否合法。
设 \(lst_i\) 表示第一个比 \(b_i\) 小的位置与当前位置的差值。换句话说，取最大的 \(j\) 使 \(a_j<b_i\)，令 \(lst_i= j-i\)。那么 \([a_l,a_r]\) 与 \([b_L,b_R]\) 合法的判断条件就是 \(L-l\le \min\{lst_L,\dots,lst_R\}\)。使用 ST 表维护。
时间复杂度 \(O(n \log^2 n)\)。
我也不知道我怎么 5min 想到这个做法调了 1h 的，所以写出来给大家看看乐子。
Solution 2
发现答案只有两种，我们先把 \(a_{2,\dots,n}\) 跟 \(b\) 匹配。
现在加了一个数，要么以上匹配还是合法，要么变不合法了，那就把新加的那个删掉，答案增加 \(1\)。于是就做完了。
Code
``` #define int long long const int N=2e5+5; int T,n,m; int a[N],b[N],d[N],L[N],tot; int st[20][N]; il bool check(int l,int r,int L,int R) { if(l>r) return 1; int len=__lg(R-L+1); int mn=min(st[len][L],st[len][R-(1< n-mid&&mid) return check(1,n-mid,mid+1,n); bool flag1=check(1,pos-1,mid+1,mid+pos-1); bool flag2=x >1; if(Check(mid,x)) r=mid; else l=mid+1; } return l; } void solve() { tot=1; n=read(),m=read(); d[1]=m; d[++tot]=1; for(int i=1;i 1) ans+=(d[i+1]-d[i]-1)*Solve(d[i]+1); } printf("%lld\n",ans); } signed main() { int T=read(); while(T--) solve(); } ```B. Time Travel
因为时间和时间不好区分，我们不妨令 \(a_i\) 叫时间，\(i\) 叫日期。
设 \(dis_i\) 表示到达点 \(i\) 的最早日期。对每条边记录它所属的时间。
把每个 \(i\) 按 \(a_i\) 分组，就可以二分出在当前 \(dis_u\) 下 \(u\to v\) 这条边可通行的最早日期。
把这个当作边权跑 dijkstra 就行了，双 \(\log\) 但是跑得挺快。
Code
const int N=2e5+5,inf=1e9;
#define pii pair<int,int>
#define fi first
#define se second
int n,t,k,a[N];
map<pii,int> mp;
struct edge{int nxt,to,id;} e[N<<1];
int head[N],cnt=1;
il void add(int u,int v,int id) {e[++cnt]={head[u],v,id};head[u]=cnt;}
vector<int> tim[N],nxt[N];
int dis[N];
il int get(int nowt,int id)
{auto ans=upper_bound(nxt[id].begin(),nxt[id].end(),nowt);if(ans==nxt[id].end()) return inf;else return *ans;
}
int main()
{n=read(),t=read();for(int i=1;i<=t;i++){int x=read();for(int j=1;j<=x;j++){int u=read(),v=read();add(u,v,i),add(v,u,i);}}k=read();for(int i=1;i<=k;i++) a[i]=read(),nxt[a[i]].push_back(i);priority_queue<pii,vector<pii>,greater<pii> >q;for(int i=1;i<=n;i++) dis[i]=inf;dis[1]=0,q.push(pii(0,1));while(!q.empty()){int u=q.top().se,f=q.top().fi; q.pop();if(dis[u]!=f) continue;for(int i=head[u];i;i=e[i].nxt){int v=e[i].to,id=e[i].id;int w=get(dis[u],id);if(dis[v]>w) dis[v]=w,q.push(pii(dis[v],v));}}if(dis[n]==inf) printf("-1\n");else printf("%d\n",dis[n]);return 0;
}C. Minimum Array
被 A2 卡没时间了 /oh
Description
给一个长度为 \(n\) 的初始序列 \(a\) 和 \(q\) 次操作。每次操作形如给 \(a_l\sim a_r\) 的值加上 \(k\)。
依次进行这些操作，求过程中得到过字典序最小的序列。
$n,q\le 5\times 105, -109\le a_i,k\le 10^9 $。
Solution 1
考虑依次进行每个操作，维护当前能使答案字典序最小的操作编号 \(ans\)。
只考虑从上一个 \(ans\) 到当前时刻的操作，设它们操作后形成的序列为 \(b\)。那么当前的实际序列就是 \([1,ans]\) 的实际序列与 \(b\) 数组对应位相加后的结果。
当前序列比 \([1,ans]\) 字典序更小的充要条件是 \(b\) 中第一个不为 \(0\) 的位置的值 \(<0\)，证明是显然的。每次修改后判断，满足这个条件就更新 \(ans\)，并清零 \(b\) 数组。
也就是说我们只需要一个数据结构支持区间加、求第一个不为 \(0\) 的位置、单点求值。
直接上线段树是可做的。不过发现第一个不为 \(0\) 的位置只能是某个 \(l_i\) 或 \(r_i+1\)，所以把这些点塞进 set 里暴力判断即可，区间加用树状数组维护。
Solution 2
看了下官方题解。
我们直接在差分数组上考虑这个问题，修改变成了单点，更新答案还是求第一个不为 \(0\) 的位置。这样就不用写树状数组了。
