慕枫宁波网站建设,质量品质好的装修公司,广州网站开发企业,云南网站建设工具D - LIS 2
因为没有让你求方案数#xff0c;所以还是比较好做的。
如果每一个连续段都退化成一个点#xff0c;那么答案就是直接求 L I S LIS LIS。
否则#xff0c;假设我们选了一些连续段把它们拼起来形成答案#xff0c;显然我们有 r i 1 ≥ l i r_{i1}\ge l_i ri1…D - LIS 2
因为没有让你求方案数所以还是比较好做的。
如果每一个连续段都退化成一个点那么答案就是直接求 L I S LIS LIS。
否则假设我们选了一些连续段把它们拼起来形成答案显然我们有 r i 1 ≥ l i r_{i1}\ge l_i ri1≥li否则这两段不能同时存在并且其中一段不能包含另一段否则可以把另一段删去。那么如果 l i 1 r i l_{i1}r_i li1ri答案显然就是两段的长度加起来如果 l i 1 ≥ r i l_{i1}\ge r_i li1≥ri那么中间那一段重复的部分不管它答案是 r i 1 − l i 1 r_{i1}-l_i1 ri1−li1。
用线段树维护就做完了。复杂度 O ( n log n ) O(n\log n) O(nlogn)。
E - Difference Sum Query
非常好的谜题。但是我不会。
首先根据 a i b i \frac{a_i}{b_i} biai的范围不难得出新的区间长度不会超过原长度的 2 3 \frac{2}{3} 32因此 X i ≤ log N X_i\le \log N Xi≤logN。
然后根据 { X i } \{X_i\} {Xi}的构造过程我们可以建立一颗二叉树那么一个点的值就是它的深度。显然 i i i和 i 1 i1 i1之间是存在祖先关系的因此问题转化为从 l l l走到 l 1 , . . . , r l1,...,r l1,...,r过程中经过的路径长度。
做到这一步感觉非常不可做。我们需要非常神奇的结论假设让 r r r重新走回 l l l那么答案就是 [ l , r ] [l,r] [l,r]之间的点组成的虚树的边的数目乘 2 2 2。这非常好理解因为上述过程恰好就是做了一遍 D F S DFS DFS。今天思路实在是非常混乱不过我们还是尝试证明一下这个结论。事实上我们只需要用到因为是二叉搜索树所以子树内编号是连续的因此进入一个子树后会把会把子树内能走的点走完出去后就再也进不来了。
那么我们只要求出虚树点的数目即可。显然只需要求 l , r l,r l,r路径上的编号不在 [ l , r ] [l,r] [l,r]之间的点的数目复杂度 O ( log n ) O(\log n) O(logn)。
就这样吧。今日状态不佳。
#includebits/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);cinnm;for(int i0;im;i)cina[i]b[i];cinQ;while(Q--){ll c,d;cincd;ll l1,rn;ll numc0,depc0,t0;while(1){ll M(l*a[t]r*b[t])/(a[t]b[t]);if(Mc)break;if(Mc){numc,lM1;}else rM-1;t(t1)%m;depc;}l1,rn;ll numd0,depd0;t0;while(1){ll M(l*a[t]r*b[t])/(a[t]b[t]);if(Md)break;if(Md){numd,rM-1;}else lM1;t(t1)%m;depd;}ll res2*(numcnumdd-c)-depc-depd;coutres\n;}
}F - Good Division
最近只会抄 std \text{std} std了算了摆了
首先一眼真 不难看出序列合法的充要条件是不存在绝对众数。
然后似乎也没有什么特别好的思路不妨还是尝试一下当确定绝对众数为 v v v的情形并且我们用总方案数减去不合法的方案数。那么将 ( a 2 i − 1 , a 2 i ) (a_{2i-1},a_{2i}) (a2i−1,a2i)看成一个权值在 [ − 1 , 1 ] [-1,1] [−1,1]之间的数记作 b i b_i bi我们需要对后缀和 0 0 0的位置求和。
让我们跳出这个 d p dp dp。考虑对于固定的 v v v如果对位置 i i i造成影响那么一定存在 j i ji ji使得 S j S i S_jS_i SjSi。分析可知这样的 i i i不会超过 c n t v cnt_v cntv个。
同时对于一个 j j j我们还要知道它会对那些 v v v造成贡献。显然这样的 j j j也不会超过 c n t v cnt_v cntv个。
那么将这些信息预处理出来即可。注意还是要写离散化。
复杂度 O ( n log n ) O(n\log n) O(nlogn)。
没什么状态就写一下代码吧
反思这道题做了两个下午才 A A A掉说明自己的代码能力还是不够或者说想得还是不够。应该引起重视。
#includebits/stdc.h
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
const int N2e65;
const int mod998244353;
int n,a[N],cnt[N],*f[N];
int bit[N*2],len,dp[N];
vectorpairint,intG[N];
vectorpairint,intmaj[N];
vectorpairint,intmaj2[N];
vectorintlsh[N];
int qry(int v,int x){int tot(0);for(;x;x-x-x)tot(totf[v][x])%mod;return tot;
}
void upd(int v,int x,int y){for(;x2*cnt[v];xx-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);cinn;for(int i1;i2*n;i)cina[i],cnt[a[i]];//fixedfor(int i1;i2*n;i)f[i]bitlen,len2*cnt[i]1;for(int i1;in;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 i1;i2*n;i){int sumnow0,sumpre0,pos0,sumval-n;for(auto x:G[i]){while(sumnow-1sumprepos1x.fi)sumnow--,pos,maj[pos].pb({i,sumnow}),lsh[i].pb(sumnow);sumnow-x.fi-pos-1;//全是-1sumpremin(sumpre,sumnow);posx.fi;if((sumnowx.se)sumpre)maj[x.fi].pb({i,sumnow}),lsh[i].pb(sumnow);sumval1x.se;}while(sumnow-1sumprepos1n)sumnow--,pos,maj[pos].pb({i,sumnow}),lsh[i].pb(sumnow);reverse(G[i].begin(),G[i].end());sumnow0,sumpre0,posn1;for(auto x:G[i]){while(sumnow-1sumprepos-1x.fi)sumnow--,pos--,maj2[pos-1].pb({i,sumval-sumnow}),lsh[i].pb(sumval-sumnow);sumnow-pos-x.fi-1;sumpremin(sumpre,sumnow);posx.fi;if((sumnowx.se)sumpre){maj2[pos-1].pb({i,sumval-sumnow}),lsh[i].pb(sumval-sumnow);}}while(sumnow-1sumprepos-11)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 sumpre1;for(int i0;in;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(sumpredp[i])%mod;}cout(dp[n]mod)%mod\n;
}
