题意

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

感想

这题的话，我做完之后，发现我是当前所有人中最慢的。。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; }