本文共 688 字，大约阅读时间需要 2 分钟。

题目

思路

类似于treap，每个节点的编号满足二叉搜索树的性质。节点 i 的权值为 $p_i$​，每个节点的权值满足小根堆的性质。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int n,a[10000008][4],tot;inline int read(){   	int f=0;	char c=getchar();	while (c<'0'||c>'9') c=getchar();	while (c>='0'&&c<='9') f=f*10+c-'0',c=getchar();	return f;}int main(){   	n=read();	for (int i=1;i<=n;i++) a[i][0]=read();	a[++tot][1]=0;	for (int i=1;i<=n;i++)	{   		while (tot&&a[a[tot][1]][0]>a[i][0]) a[i][2]=a[tot--][1];		if (a[tot][1]) a[a[tot][1]][3]=i;		a[++tot][1]=i;	}	long long l=0,r=0;	for (int i=1;i<=n;i++) l^=1ll*i*(a[i][2]+1),r^=1ll*i*(a[i][3]+1);	cout<
        
         <<' '<
        
       
      
     
    
   

转载地址：http://vnye.baihongyu.com/