A1. Dances (Easy version)
把 a,b 序列都从小到大排序，a 贪心删大的，b 贪心删小的，二分答案并 O(n) 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≤109，肯定不能一个一个求答案。但是发现我们只关心这个 a1 和 a,b 中其余的每个元素的大小关系。也就是说我们只要枚举 4×105 种大小关系，对他们分别求解就可以得到所有答案了。
原来对一个给定序列求答案的时间复杂度是 O(nlogn)，考虑优化这个过程。
同样二分删掉的数量 mid，设 a1=x，a 序列排序时不包含 a1。
那么把 x 插进 a 的对应位置，需要判断的区间可以分成 3 段：a 序列中在 x 前的部分，x 的位置，a 序列中在 x 后的部分。
已经有两个 log 了，需要 O(1) 地判断 [al,ar] 与 [bL,bR] 对应起来是否合法。
设 lsti 表示第一个比 bi 小的位置与当前位置的差值。换句话说，取最大的 j 使 aj<bi，令 lsti=j−i。那么 [al,ar] 与 [bL,bR] 合法的判断条件就是 L−l≤min{lstL,…,lstR}。使用 ST 表维护。
时间复杂度 O(nlog2n)。
我也不知道我怎么 5min 想到这个做法调了 1h 的，所以写出来给大家看看乐子。
Solution 2
发现答案只有两种，我们先把 a2,…,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
因为时间和时间不好区分，我们不妨令 ai 叫时间，i 叫日期。
设 disi 表示到达点 i 的最早日期。对每条边记录它所属的时间。
把每个 i 按 ai 分组，就可以二分出在当前 disu 下 u→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 次操作。每次操作形如给 al∼ar 的值加上 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 的位置只能是某个 li 或 ri+1，所以把这些点塞进 set 里暴力判断即可，区间加用树状数组维护。
Solution 2
看了下官方题解。
我们直接在差分数组上考虑这个问题，修改变成了单点，更新答案还是求第一个不为 0 的位置。这样就不用写树状数组了。