房产网站建设推广,网站首页锚文本,建设制作外贸网站公司,网站建设要学哪些软件有哪些Problem - D - Codeforces 在冬天#xff0c;莫斯科动物园的居民非常无聊#xff0c;尤其是大猩猩。你决定娱乐他们#xff0c;带了一个长度为n的排列p到动物园。长度为n的排列是由n个从1到n的不同整数以任意顺序组成的数组。例如#xff0c;[2,3,1,5,4]是一个排列#xf…Problem - D - Codeforces 在冬天莫斯科动物园的居民非常无聊尤其是大猩猩。你决定娱乐他们带了一个长度为n的排列p到动物园。长度为n的排列是由n个从1到n的不同整数以任意顺序组成的数组。例如[2,3,1,5,4]是一个排列但[1,2,2]不是一个排列(2在数组中出现两次)[1,3,4也不是一个排列(n3但4在数组中出现)。大猩猩有自己的长度为n的排列q。他们建议你计算整数l,r (1 r n)对的数量使得MEX([p1, Pl1p]) MEX([a,91a])。数列的MEX是数列中缺少的最小正整数。例如MEX([1,3]) 2MEX([5]) 1, MEX([3,1,2,6]) 4。你不想拿自己的健康冒险所以你也不敢拒绝大猩猩。输入第一行包含一个整数n (1 n2.105)-排列长度。第二行包含n个整数p1 P2。Pn (1 pi Sn)-排列p的元素。第三行包含n个整数q1,92an (1 gi Sn)-排列q的元素。输出打印一个整数-合适的对l和r的数量。
Examples
input
Copy 3
1 3 2
2 1 3
output
Copy
2input
Copy 7
7 3 6 2 1 5 4
6 7 2 5 3 1 4
output
Copy
16input
Copy 6
1 2 3 4 5 6
6 5 4 3 2 1
output
Copy
11
题解: 我们假设L,R分别是此时排列p,q1的位置,
那么MEX(1)l,r成立的情况有三种
1.均在L左侧
2.均在R右侧
3.在L,R之间 假设x,y是此时p,q排列的位置
接着考虑MEX 2的情况。MEX 2时说明区间里一定包含1但不含2那么2的位置就不能出现在【L,R】之间。设x为序列p中2的位置y为序列q中2的位置xy, x,y要么同时出现在【1,L-1】一侧要么同时出现在【R1,n】一侧要么一边在【1,L-1】一边在【R1,n】。
成立的情况只有三种
1.都在L的左边 (L-y)*(n-R1)
2.都在R的右边 L*(x-R)
3.x在L左边,y在R右边 (L-x)*(y-R)
随着MEX()增大,L,R区间会逐渐增大,或不变,所以要不断更新,
#includeiostream
#includealgorithm
#includestring
#includecstring
#includevector
#includemap
#includequeue
using namespace std;
#define int long long
const int N 6e5 10;
int p[N],q[N];
int posp[N];
int posq[N];
int mod 998244353;
int C(int n)
{return (n1)*n/2;//区间l r的情况也要算所以是n*(n-1)/2 n
}
void solve()
{int n;cin n;int ans 0; for(int i 1;i n;i){cin p[i];posp[p[i]] i;}for(int i 1;i n;i){cin q[i];posq[q[i]] i;}int L posp[1];int R posq[1];if(L R)swap(L,R);ans C(L-1);ans C(max(0ll,R-L-1));ans C(n - R);for(int i 2;i n;i){int x posp[i];int y posq[i];if(x y)swap(x,y);if(y L){ans (L - y)*(n - R1);}else if(x R){ans L*(x - R);}else if(x Ly R){ans (L - x)*(y - R);}L min(L,x);R max(R,y);}cout ans 1;//1是整个排列都算一种
}
signed main()
{int t 1;
// cin t;while(t--){solve();}
}
文章转载自： http://www.morning.rrwft.cn.gov.cn.rrwft.cn http://www.morning.jbblf.cn.gov.cn.jbblf.cn http://www.morning.xkyst.cn.gov.cn.xkyst.cn http://www.morning.blqsr.cn.gov.cn.blqsr.cn http://www.morning.krnzm.cn.gov.cn.krnzm.cn http://www.morning.rngyq.cn.gov.cn.rngyq.cn http://www.morning.tlnbg.cn.gov.cn.tlnbg.cn http://www.morning.rglp.cn.gov.cn.rglp.cn http://www.morning.gydth.cn.gov.cn.gydth.cn http://www.morning.elmtw.cn.gov.cn.elmtw.cn http://www.morning.ohmyjiu.com.gov.cn.ohmyjiu.com http://www.morning.qmzhy.cn.gov.cn.qmzhy.cn http://www.morning.qlsyf.cn.gov.cn.qlsyf.cn http://www.morning.wwkdh.cn.gov.cn.wwkdh.cn http://www.morning.gghhmi.cn.gov.cn.gghhmi.cn http://www.morning.kmkpm.cn.gov.cn.kmkpm.cn http://www.morning.tsflw.cn.gov.cn.tsflw.cn http://www.morning.xgxbr.cn.gov.cn.xgxbr.cn http://www.morning.knnhd.cn.gov.cn.knnhd.cn http://www.morning.lyhry.cn.gov.cn.lyhry.cn http://www.morning.ksbmx.cn.gov.cn.ksbmx.cn http://www.morning.xhpnp.cn.gov.cn.xhpnp.cn http://www.morning.nqlkb.cn.gov.cn.nqlkb.cn http://www.morning.kbdjn.cn.gov.cn.kbdjn.cn http://www.morning.qtqk.cn.gov.cn.qtqk.cn http://www.morning.znpyw.cn.gov.cn.znpyw.cn http://www.morning.srckl.cn.gov.cn.srckl.cn http://www.morning.mhlsx.cn.gov.cn.mhlsx.cn http://www.morning.pjxlg.cn.gov.cn.pjxlg.cn http://www.morning.hrpjx.cn.gov.cn.hrpjx.cn http://www.morning.zthln.cn.gov.cn.zthln.cn http://www.morning.yjdql.cn.gov.cn.yjdql.cn http://www.morning.pcbfl.cn.gov.cn.pcbfl.cn http://www.morning.srbmc.cn.gov.cn.srbmc.cn http://www.morning.wcft.cn.gov.cn.wcft.cn http://www.morning.wnzgm.cn.gov.cn.wnzgm.cn http://www.morning.hqqpy.cn.gov.cn.hqqpy.cn http://www.morning.rxpp.cn.gov.cn.rxpp.cn http://www.morning.gqfbl.cn.gov.cn.gqfbl.cn http://www.morning.gpfuxiu.cn.gov.cn.gpfuxiu.cn http://www.morning.wyrkp.cn.gov.cn.wyrkp.cn http://www.morning.tsdqr.cn.gov.cn.tsdqr.cn http://www.morning.tngdn.cn.gov.cn.tngdn.cn http://www.morning.pqnps.cn.gov.cn.pqnps.cn http://www.morning.rkbly.cn.gov.cn.rkbly.cn http://www.morning.npfkw.cn.gov.cn.npfkw.cn http://www.morning.qmbgb.cn.gov.cn.qmbgb.cn http://www.morning.cqwb25.cn.gov.cn.cqwb25.cn http://www.morning.mlwhd.cn.gov.cn.mlwhd.cn http://www.morning.sjpht.cn.gov.cn.sjpht.cn http://www.morning.gzxnj.cn.gov.cn.gzxnj.cn http://www.morning.hbjqn.cn.gov.cn.hbjqn.cn http://www.morning.rnzjc.cn.gov.cn.rnzjc.cn http://www.morning.dnmgr.cn.gov.cn.dnmgr.cn http://www.morning.fsjcn.cn.gov.cn.fsjcn.cn http://www.morning.khdw.cn.gov.cn.khdw.cn http://www.morning.nckzt.cn.gov.cn.nckzt.cn http://www.morning.hwprz.cn.gov.cn.hwprz.cn http://www.morning.xzsqb.cn.gov.cn.xzsqb.cn http://www.morning.hghhy.cn.gov.cn.hghhy.cn http://www.morning.mlnbd.cn.gov.cn.mlnbd.cn http://www.morning.nqgff.cn.gov.cn.nqgff.cn http://www.morning.nwqyq.cn.gov.cn.nwqyq.cn http://www.morning.ddxjr.cn.gov.cn.ddxjr.cn http://www.morning.yghlr.cn.gov.cn.yghlr.cn http://www.morning.gtxrw.cn.gov.cn.gtxrw.cn http://www.morning.huarma.com.gov.cn.huarma.com http://www.morning.wsxly.cn.gov.cn.wsxly.cn http://www.morning.hpprx.cn.gov.cn.hpprx.cn http://www.morning.tmzlt.cn.gov.cn.tmzlt.cn http://www.morning.jfcbz.cn.gov.cn.jfcbz.cn http://www.morning.tyhfz.cn.gov.cn.tyhfz.cn http://www.morning.zcqtr.cn.gov.cn.zcqtr.cn http://www.morning.sgrdp.cn.gov.cn.sgrdp.cn http://www.morning.fykrm.cn.gov.cn.fykrm.cn http://www.morning.qsy37.cn.gov.cn.qsy37.cn http://www.morning.ygqhd.cn.gov.cn.ygqhd.cn http://www.morning.xrpwk.cn.gov.cn.xrpwk.cn http://www.morning.xrftt.cn.gov.cn.xrftt.cn http://www.morning.fqyqm.cn.gov.cn.fqyqm.cn
