题意

题意不贴了。。自己看。。

感想

这题的话，我做完之后，发现我是当前所有人中最慢的。。bzoj垫底成就达成。。
然后我上网一看，我的方法似乎十分地。。与众不同啊。。
好像是全部人中代码最长+空间最大+时间最慢+最容易想到

题解

说一下我的挫做法吧。。
一开始我考虑的是括号序列。。然而发现这题似乎和这个没什么关系，因为他的括号虽然一一对应，但对应法则不同
然后就想到了线段。。
转化下题意，就是给你n条线段，然后问，对于第i条线段，如果把他当做a，那么他对答案的贡献就是有多少线段与他相交
也就是左端点在他的l，r之间，右端点在r之外
于是我就对每条线段按l值排了序
然后就可以二分出那些线段的左端点在区间内了。。
然后就相当于问这些线段有多少个右端点在区间外
这个显然可以用线段树合并来做
然后就没有了
时间复杂度$O(n*logn)$，但应该常熟比用树状数组的大。。
讲真我这是一个只适合我这种几乎只会线段树的人。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=100005;
struct qq
{int l,r;
}s[N];
int n;
bool cmp (qq a,qq b){
   return a.l<b.l;}
int root[N],num=0;//前i条线段
int c[N*20];
int s1[N*20],s2[N*20];
void change (int &now,int l,int r,int x)//表示在x这个地方出现了右端点 
{if (now==0) now=++num;if (l==r){c[now]++;return ;}int mid=(l+r)>>1;if (x<=mid) change(s1[now],l,mid,x);else change(s2[now],mid+1,r,x);c[now]=c[s1[now]]+c[s2[now]];
}
int Get (int rt1,int rt2,int L,int R,int l,int r)
{if (l>r) return 0;//printf("%d %d %d %d %d %d\n",rt1,rt2,L,R,l,r);if (l==L&&r==R) return c[rt1]-c[rt2];int mid=(L+R)>>1;if (r<=mid) return Get(s1[rt1],s1[rt2],L,mid,l,r);else if (l>mid) return Get(s2[rt1],s2[rt2],mid+1,R,l,r);else return Get(s1[rt1],s1[rt2],L,mid,l,mid)+Get(s2[rt1],s2[rt2],mid+1,R,mid+1,r);
}
int get (int x)//找到第一个l大于他的 
{int ans=0;int l=1,r=n;while (l<=r){int mid=(l+r)>>1;if (s[mid].l<x) {l=mid+1;ans=mid;}else r=mid-1;}return ans;
}
void Merge (int &rt1,int rt2)
{if (rt2==0) return ;if (rt1==0) {rt1=rt2;return ;}c[rt1]+=c[rt2];Merge(s1[rt1],s1[rt2]);Merge(s2[rt1],s2[rt2]);return ;
}
int main()
{scanf("%d",&n);for (int u=1;u<=n*2;u++){int x;scanf("%d",&x);if (s[x].l==0)  s[x].l=u;else s[x].r=u;}sort(s+1,s+1+n,cmp);//按l值递增 for (int u=1;u<=n;u++)  {change(root[u],1,n*2,s[u].r);Merge(root[u],root[u-1]);}int ans=0;for (int u=1;u<=n;u++)//吧这个当做a值看看 {int i=get(s[u].r);if (i==0) continue;ans=ans+Get(root[i],root[u],1,n*2,s[u].r+1,n*2);//printf("YES:%d %d %d\n",u,i,ans);}printf("%d\n",ans);return 0;
}