D - LIS 2

因?yàn)闆]有讓你求方案數(shù)，所以還是比較好做的。

如果每一個(gè)連續(xù)段都退化成一個(gè)點(diǎn)，那么答案就是直接求$LIS$。

否則，假設(shè)我們選了一些連續(xù)段把它們拼起來形成答案，顯然我們有$r_{i+1}\ge l_i$，否則這兩段不能同時(shí)存在；并且其中一段不能包含另一段，否則可以把另一段刪去。那么，如果$l_{i+1}>r_i$，答案顯然就是兩段的長(zhǎng)度加起來；如果$l_{i+1}\ge r_i$，那么中間那一段重復(fù)的部分不管它，答案是$r_{i+1}?l_i+1$。

用線段樹維護(hù)就做完了。復(fù)雜度$O(n\log n)$。

E - Difference Sum Query

非常好的謎題。但是我不會(huì)。

首先，根據(jù)$\frac{a_i}{b_i}$的范圍不難得出新的區(qū)間長(zhǎng)度不會(huì)超過原長(zhǎng)度的$\frac{2}{3}$，因此$X_i\le \log N$。

然后，根據(jù) { X i } \{X_i\} {Xi?}的構(gòu)造過程，我們可以建立一顆二叉樹，那么一個(gè)點(diǎn)的值就是它的深度。顯然$i$和$i+1$之間是存在祖先關(guān)系的，因此問題轉(zhuǎn)化為從$l$走到$l+1,...,r$過程中經(jīng)過的路徑長(zhǎng)度。

做到這一步，感覺非常不可做。我們需要非常神奇的結(jié)論：假設(shè)讓$r$重新走回$l$，那么答案就是$[l,r]$之間的點(diǎn)組成的虛樹的邊的數(shù)目乘$2$。這非常好理解，因?yàn)樯鲜鲞^程恰好就是做了一遍$DFS$。今天思路實(shí)在是非?；靵y，不過我們還是嘗試證明一下這個(gè)結(jié)論。事實(shí)上我們只需要用到：因?yàn)槭嵌嫠阉鳂?#xff0c;所以子樹內(nèi)編號(hào)是連續(xù)的，因此進(jìn)入一個(gè)子樹后會(huì)把會(huì)把子樹內(nèi)能走的點(diǎn)走完，出去后就再也進(jìn)不來了。

那么我們只要求出虛樹點(diǎn)的數(shù)目即可。顯然只需要求$l,r$路徑上的編號(hào)不在$[l,r]$之間的點(diǎn)的數(shù)目，復(fù)雜度$O(\log n)$。

就這樣吧。今日狀態(tài)不佳。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
ll n,m,Q,a[105],b[105];
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=0;i<m;i++)cin>>a[i]>>b[i];cin>>Q;while(Q--){ll c,d;cin>>c>>d;ll l=1,r=n;ll numc=0,depc=0,t=0;while(1){ll M=(l*a[t]+r*b[t])/(a[t]+b[t]);if(M==c)break;if(M<c){numc++,l=M+1;}else r=M-1;t=(t+1)%m;depc++;}l=1,r=n;ll numd=0,depd=0;t=0;while(1){ll M=(l*a[t]+r*b[t])/(a[t]+b[t]);if(M==d)break;if(M>d){numd++,r=M-1;}else l=M+1;t=(t+1)%m;depd++;}ll res=2*(numc+numd+d-c)-depc-depd;cout<<res<<"\n";}
}

F - Good Division

最近只會(huì)抄$\text{std}$了，算了擺了

首先一眼真 不難看出序列合法的充要條件是不存在絕對(duì)眾數(shù)。

然后似乎也沒有什么特別好的思路，不妨還是嘗試一下當(dāng)確定絕對(duì)眾數(shù)為$v$的情形，并且我們用總方案數(shù)減去不合法的方案數(shù)。那么將$(a_{2i?1},a_{2i})$看成一個(gè)權(quán)值在$[?1,1]$之間的數(shù)（記作$b_i$），我們需要對(duì)后綴和$>0$的位置求和。

讓我們跳出這個(gè)$dp$?？紤]對(duì)于固定的$v$，如果對(duì)位置$i$造成影響，那么一定存在$j<i$，使得$S_j<S_i$。分析可知，這樣的$i$不會(huì)超過$cn{t}_v$個(gè)。

同時(shí)對(duì)于一個(gè)$j$，我們還要知道它會(huì)對(duì)那些$v$造成貢獻(xiàn)。顯然這樣的$j$也不會(huì)超過$cn{t}_v$個(gè)。

那么將這些信息預(yù)處理出來即可。注意還是要寫離散化。

復(fù)雜度$O(n\log n)$。

沒什么狀態(tài)就寫一下代碼吧

反思：這道題做了兩個(gè)下午才$A$掉，說明自己的代碼能力還是不夠（或者說想得還是不夠）。應(yīng)該引起重視。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
const int N=2e6+5;
const int mod=998244353;
int n,a[N],cnt[N],*f[N];
int bit[N*2],len,dp[N];
vector<pair<int,int>>G[N];
vector<pair<int,int>>maj[N];
vector<pair<int,int>>maj2[N];
vector<int>lsh[N];
int qry(int v,int x){int tot(0);for(;x;x-=x&-x)tot=(tot+f[v][x])%mod;return tot;
}
void upd(int v,int x,int y){for(;x<=2*cnt[v];x+=x&-x)f[v][x]=(f[v][x]+y)%mod;
}
int get(int x,int y){return lower_bound(lsh[x].begin(),lsh[x].end(),y)-lsh[x].begin()+1;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=2*n;i++)cin>>a[i],cnt[a[i]]++;//fixedfor(int i=1;i<=2*n;i++)f[i]=bit+len,len+=2*cnt[i]+1;for(int i=1;i<=n;i++){if(a[2*i-1]==a[2*i]){G[a[2*i-1]].pb({i,1});}else{G[a[2*i-1]].pb({i,0});G[a[2*i]].pb({i,0});}}//fixedfor(int i=1;i<=2*n;i++){int sumnow=0,sumpre=0,pos=0,sumval=-n;for(auto x:G[i]){while(sumnow-1>sumpre&&pos+1<x.fi)sumnow--,pos++,maj[pos].pb({i,sumnow}),lsh[i].pb(sumnow);sumnow-=x.fi-pos-1;//全是-1sumpre=min(sumpre,sumnow);pos=x.fi;if((sumnow+=x.se)>sumpre)maj[x.fi].pb({i,sumnow}),lsh[i].pb(sumnow);sumval+=1+x.se;}while(sumnow-1>sumpre&&pos+1<=n)sumnow--,pos++,maj[pos].pb({i,sumnow}),lsh[i].pb(sumnow);reverse(G[i].begin(),G[i].end());sumnow=0,sumpre=0,pos=n+1;for(auto x:G[i]){while(sumnow-1>sumpre&&pos-1>x.fi)sumnow--,pos--,maj2[pos-1].pb({i,sumval-sumnow}),lsh[i].pb(sumval-sumnow);sumnow-=pos-x.fi-1;sumpre=min(sumpre,sumnow);pos=x.fi;if((sumnow+=x.se)>sumpre){maj2[pos-1].pb({i,sumval-sumnow}),lsh[i].pb(sumval-sumnow);}}while(sumnow-1>sumpre&&pos-1>=1)sumnow--,pos--,maj2[pos-1].pb({i,sumval-sumnow}),lsh[i].pb(sumval-sumnow);sort(lsh[i].begin(),lsh[i].end());lsh[i].erase(unique(lsh[i].begin(),lsh[i].end()),lsh[i].end());}//fixedint sumpre=1;for(int i=0;i<=n;i++){dp[i]=sumpre;for(auto x:maj[i]){dp[i]=(dp[i]-qry(x.fi,get(x.fi,x.se)-1))%mod;}for(auto x:maj2[i]){upd(x.fi,get(x.fi,x.se),dp[i]);}if(i)sumpre=(sumpre+dp[i])%mod;}cout<<(dp[n]+mod)%mod<<"\n";
}