题目大意：交互题，每次可以询问一个子区间次大值的位置，最多询问20次，问全局最大值的位置。n=1e5

40次的情况大力二分，20次需要一些技巧

设全局最大值位置为$x$

问一次全局次大值，设为$pos$，再次询问$pos$两侧判断最大值在$pos$左侧还是右侧，并把$pos$它放在后续处理区间的头或者尾

放在头/尾可以减少很多麻烦

现假设$pos$在尾，我们在$[1,pos-1]$里找$x$

每次二分一个位置$mid$，如果$mid\le x$，那么问$[mid,pos]$结果是$pos$，如果$mid>x$，结果不是$pos$

如此可找到x

1 const int N1=105; const int inf=0x3f3f3f3f;
2
3 int n,now;
4 int getx(int l,int r)
5 {
6 if(l==r) return 0;
7 printf("? %d %d\n",l,r);
8 fflush(stdout);
9 int x; scanf("%d",&x); return x;
10 }
11 void solveL(int pos)
12 {
13 int l=1,r=pos-1,mid,ans=0,k;
14 while(l<=r) 15 { 16 mid=(l+r)>>1;
17 k=getx(mid,pos);
18 if(k==pos) ans=mid, l=mid+1;
19 else r=mid-1;
20 }
21 printf("! %d\n",ans); exit(0);
22 }
23 void solveR(int pos)
24 {
25 int l=pos+1,r=n,mid,ans=0,k;
26 while(l<=r) 27 { 28 mid=(l+r)>>1;
29 k=getx(pos,mid);
30 if(k==pos) ans=mid, r=mid-1;
31 else l=mid+1;
32 }
33 printf("! %d\n",ans); exit(0);
34 }
35
36 int main()
37 {
38 scanf("%d",&n);
39 int pos=getx(1,n),k;
40 if(pos==1) solveR(1);
41 else if(pos==n) solveL(n);
42 else{
43 k=getx(1,pos);
44 if(k==pos) solveL(pos); else solveR(pos);
45 }
46 return 0;
47 }

题目大意：给出一个序列，问所有长度大于等于k的子区间中，中位数的最大值是多少，$n=2e5$

题解给了这样一个妙妙思路：

首先考虑序列都是1和-1咋做：权值和大于0的子区间的中位数是1！需要维护小于某个值的最小位置，树状数组记录前缀最小值

推广到中位数问题，二分。

每次判断中位数$\ge mid$是否可行

把小于$mid$填成-1，$\ge mid$填成1，权值和大于0的子区间的中位数$\ge mid$！和上面同样的方法做就行了

1 const int N1=400010; const int inf=0x3f3f3f3f;
2
3 int n,K,nn;
4 int a[N1],sum[N1];
5 struct bit{
6 int mi[N1];
7 void upd(int x,int w)
8 { for(int i=x;i<=nn;i+=i&(-i)) mi[i]=min(mi[i],w); } 9 int query(int x) 10 { int ans=inf; for(int i=x;i;i-=i&(-i)) ans=min(ans,mi[i]); return ans; } 11 void clr(int x) 12 { for(int i=x;i<=nn;i+=i&(-i)) mi[i]=inf; } 13 }s; 14 int check(int w) 15 { 16 memset(s.mi,0x3f,sizeof(s.mi)); 17 s.upd(n+1+0,0); 18 for(int i=1,j;i<=n;i++) 19 { 20 if(a[i]=K) return 1;
23 s.upd(n+1+sum[i],i);
24 }
25 return 0;
26 }
27
28 int main()
29 {
30 scanf("%d%d",&n,&K); nn=n+n+1;
31 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 32 int l=1,r=n,ans=0,mid; 33 while(l<=r) 34 { 35 mid=(l+r)>>1;
36 if(check(mid)) ans=mid, l=mid+1;
37 else r=mid-1;
38 }
39 printf("%d\n",ans);
40 return 0;
41 }

题目大意：给一个无向图，每次必须连着走两条边，代价为$(w1+w2)^{2}$，问从1走到其它所有点的代价最小值，$n=1e5，w\le 50$

又是一道构造妙妙题目

由于$w$很小，考虑拆点

对于一条有向边$(u,v,w)$

i是和v相连的出来的所有不同权值，$u->(v,i)$，代价$(w+i)^{2}$。 $ (u,w)->v$，代价0

考虑连着走两条边$(x,y,w1)(y,z,w2)$的情形：$x->(y,w2)->z$ 代价为$(w1+w2)^{2}$

然后最短路就行了，边数为$O(Wm)$，时间复杂度$O(Wmlogm)$

用map维护拆点可以减少点数

1 #define ite map::iterator
2 const int N1=500005; const int M1=N1*42; const ll inf=0x3f3f3f3f3f3f3f3fll;
3
4 struct edge{
5 int to[M1],nxt[M1],val[M1],head[N1],cte;
6 int ae(int u,int v,int w)
7 { cte++; to[cte]=v, nxt[cte]=head[u]; head[u]=cte; val[cte]=w; }
8 // printf("%d %d %d\n",u,v,w);
9 }e;
10 struct node{
11 int id; ll val;
12 friend bool operator < (const node &s1,const node &s2) 13 { return s1.val>s2.val; }
14 };
15 priority_queueque;
16
17 int n,m,tot;
18 int id[N1]; ll dis[N1]; bool vis[N1];
19 mapmp[N1];
20 void addmp(int u,int v,int w)
21 {
22 ite k=mp[v].find(w); int y;
23 if(k==mp[v].end()) y=++tot, mp[v][w]=tot;
24 else y=(*k).second;
25 e.ae(y,u,0);
26 }
27 void adde(int u,int v,int w1)
28 {
29 int y,w2;
30 for(ite k=mp[v].begin();k!=mp[v].end();k++)
31 {
32 w2=(*k).first; y=(*k).second;
33 e.ae(u,y,(w1+w2)*(w1+w2));
34 }
35 }
36 void dijkstra()
37 {
38 int x,j,v; node tmp;
39 memset(dis,0x3f,sizeof(dis));
40 que.push((node){1,0}); dis[1]=0;
41 while(!que.empty())
42 {
43 tmp=que.top(); que.pop(); x=tmp.id;
44 if(vis[x]) continue; vis[x]=true;
45 for(j=e.head[x];j;j=e.nxt[j])
46 {
47 v=e.to[j];
48 if(dis[v]>dis[x]+e.val[j])
49 {
50 dis[v]=dis[x]+e.val[j];
51 que.push((node){v,dis[v]});
52 }
53 }
54 }
55 }
56 int ex[N1],ey[N1],ew[N1];
57
58 int main()
59 {
60 scanf("%d%d",&n,&m);
61 tot=n;
62 for(int i=1;i<=m;i++)
63 {
64 scanf("%d%d%d",&ex[i],&ey[i],&ew[i]);
65 addmp(ex[i],ey[i],ew[i]); addmp(ey[i],ex[i],ew[i]);
66 }
67 for(int i=1;i<=m;i++)
68 {
69 adde(ex[i],ey[i],ew[i]); adde(ey[i],ex[i],ew[i]);
70 }
71 dijkstra();
72 for(int i=1;i<=n;i++)
73 if(dis[i]<inf) printf("%lld ",dis[i]);
74 else printf("-1 ");
75 puts("");
76 return 0;
77 }

题目大意：给一棵n个点的树，给出m条链，问有多少对链，相交部分只有一个点。$n,m=3e5$

考虑讨论交点情况

设两个链的$LCA$分别为$fx,fy$，唯一的交点为$p$

如果$p\ne fx$且$p\ne fy$，这种情况不存在！画一下图就能发现了，不可能交出来一个X字型

如果$p=fx$，我们把$x$这条链的贡献放到$y$里统计

如果$p=fx=fy$，我们在$p$点讨论贡献

离线每条链到树上，在端点和$LCA$统计贡献

记录$f[x]$表示以$x$点为$LCA$的链条数

$g[x]$表示以$father[x]$为$LCA$时，经过$x$点的链数。那么在$x$点统计链端点的贡献时，肯定得把$g[x]$这部分去掉，因此我们维护一个$h[x]$表示到根节点链上所有点的$f[x]-g[x]$，再记录$h[x]$的前缀和

还有一些链向下有两个端点，只减$g[x]$会导致去掉了两次贡献，需要容斥一下把它们加回来一次，用$map$维护

在$x$点统计链$LCA$的贡献时，$f[x]-1$就是贡献，最后把这部分贡献/2就行

1 const int N1=300005; const ll p=998244353;
2
3 ll qpow(ll x,ll y)
4 {
5 ll ans=1;
6 for(;y;x=x*x%p,y>>=1) if(y&1) ans=ans*x%p;
7 return ans;
8 }
9 struct EDGE{
10 int to[N1*2],nxt[N1*2],head[N1],cte;
11 void ae(int u,int v)
12 { cte++; to[cte]=v; nxt[cte]=head[u]; head[u]=cte; }
13 }e;
14
15 int n,m;
16 int ff[N1][20],dep[N1];
17 struct node{
18 int x,y;
19 friend bool operator < (const node &s1,const node &s2) 20 { 21 if(s1.x!=s2.x) return s1.x=0;j--) if(dep[ff[x][j]]>=dep[y]) x=ff[x][j];
44 if(x==y) return x;
45 int ans=0;
46 for(int j=19;j>=0;j--)
47 {
48 if(ff[x][j]==ff[y][j]) ans=ff[x][j];
49 else x=ff[x][j], y=ff[y][j];
50 }
51 return ans;
52 }
53 int jump(int x,int d)
54 {
55 for(int j=19;j>=0;j--) if(dep[ff[x][j]]>=d)
56 x=ff[x][j];
57 return x;
58 }
59
60 struct PATH{
61 int x,y,fa,fx,fy;
62 }pa[N1];
63 ll f[N1],g[N1];
64 ll h[N1],sh[N1];
65 vectorqp[N1],ql[N1];
66 maptwo;
67
68 ll ans1,ans2;
69 void calc_lca(int u)
70 {
71 int x,y,fa,fx,fy;
72 for(int k=0;kfy) swap(x,y), swap(fx,fy);
130 f[fa]++; g[fx]++; g[fy]++; two[(node){fx,fy}]++;
131 qp[x].push_back(i); qp[y].push_back(i); ql[fa].push_back(i);
132 }
133 pa[i].x=x, pa[i].y=y, pa[i].fa=fa, pa[i].fx=fx, pa[i].fy=fy;
134 }
135 dfs1(1); ans1=ans1+ ans2/2;
136 printf("%lld\n",ans1);
137 return 0;
138 }