瑞安 网站建设培训,做网站的图片大全,网页图片加载失败,ui设计交付物都包含哪些E. Range Deleting
首先不难知道如果f(l,r)f(l,r)f(l,r)满足题意#xff0c;那么f(l,r1),f(l,r2),…,f(l,x)f(l,r1),f(l,r2),\dots,f(l,x)f(l,r1),f(l,r2),…,f(l,x)都满足题意。 因而对于每一个左端点lll#xff0c;需要找到最小的一个右端点rrr
单调性#xff1a;对于每…E. Range Deleting
首先不难知道如果f(l,r)f(l,r)f(l,r)满足题意那么f(l,r1),f(l,r2),…,f(l,x)f(l,r1),f(l,r2),\dots,f(l,x)f(l,r1),f(l,r2),…,f(l,x)都满足题意。 因而对于每一个左端点lll需要找到最小的一个右端点rrr
单调性对于每一个左端点lll当左端点右移增大的过程中右端点也一定右移增大 有了上述单调性考虑双指针表示f(i,j)f(i,j)f(i,j)
预处理出以下数组 ①l[i]值是i的最小数组下标 ②r[i]值是i的最大数组下标 ③ll[i]值是i~x的最小数组下标 ④rr[i]值是1~i的最大数组下标
对于一个区间[l,r][l,r][l,r]假设值在[1,l−1][1,l-1][1,l−1]以及[r1,x][r1,x][r1,x]内部不存在逆序对只需要判断[1,l−1][1,l-1][1,l−1]和[r1,x][r1,x][r1,x]之间是否存在逆序对即值在[1,l−1][1,l-1][1,l−1]最大数组下标是否大于[r1,x][r1,x][r1,x]最小数组下标即如果存在逆序对rr[l-1]ll[r1]不满足条件只需根据此调整双指针位置。
对于假设条件显然可以求出对于[1,pl)[1,pl)[1,pl)内部不存在逆序对以及(pr,x](pr,x](pr,x]内部不存在逆序对因而只需要让指针iii在[1,pl][1,pl][1,pl]之间而指针jjj在[pr,x][pr,x][pr,x]之间即可。
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#pragma GCC optimize(2)
#includecstring
#includeiostream
#includealgorithm
using namespace std;
constexpr int N1000010;
int a[N],n,x;
int l[N],r[N],ll[N],rr[N];
int main()
{IO;cinnx;memset(l,0x3f,sizeof l);memset(ll,0x3f,sizeof ll);memset(r,-1,sizeof r);memset(rr,-1,sizeof rr);for(int i1;in;i){cina[i];l[a[i]]min(l[a[i]],i);r[a[i]]max(r[a[i]],i);}// rr[i] 1~i最右边的位置// ll[i] i~x最左边的位置for(int i1;ix;i) rr[i]max(rr[i-1],r[i]);for(int ix;i1;i--) ll[i]min(ll[i1],l[i]);long long res0;// [1,pl) 以及 (pr,x] 不存在逆序对int pl1,prx;while(plxrr[pl-1]l[pl]) pl;while(pr1ll[pr1]r[pr]) pr--; for(int i1,jpr;ipl;i){while(jx(ji||rr[i-1]ll[j1])) j;resx-j1;}coutres\n;return 0;
}要加油哦~
