【牛客】子串（思维、扫描线）
90nwyn
2020-09-25 15:14:46
[题目链接](https://ac.nowcoder.com/acm/contest/7329/E)
------------
枚举区间的右端点，求合法的左端点数
------------
```cpp
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&-x)
typedef long long ll;
const int M=2e6+5;
int n,p[M],pos[M],l[M],r[M],tot,c[M];
ll ans;
struct d
{
int t,x,v;
bool operator<(const d &a)const{return t<a.t;}
}opt[M];
void upd(int x,int v){for(int i=x;i<=n;i+=lowbit(i))c[i]+=v;}
int que(int x){int res=0;for(int i=x;i;i-=lowbit(i))res+=c[i];return res;}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&p[i]);
pos[p[i]]=i;
}
for(int i=1;i<=n;i++)
{
l[i]=i;
if(p[i]<=i)while(l[i]>1&&p[l[i]-1]<=i)l[i]=l[l[i]-1];
}
for(int i=n;i>=1;i--)
{
r[i]=i;
if(p[i]>=i)while(r[i]<n&&p[r[i]+1]>=i)r[i]=r[r[i]+1];
}
for(int i=1;i<=n;i++)if(i<=pos[i]&&pos[i]<=r[i])opt[++tot]={pos[i],i,1},opt[++tot]={r[i]+1,i,-1};
sort(opt+1,opt+1+tot);
for(int now=1,i=1;i<=n;i++)
{
while(now<=tot&&opt[now].t<=i)upd(opt[now].x,opt[now].v),now++;
if(l[i]<=pos[i]&&pos[i]<=i)ans+=que(pos[i])-que(l[i]-1);
}
printf("%lld\n",ans);
return 0;
}
```
------------
满足题意的区间必然有
$l$ $oxr$ $(l+1)$ $...$ $r$ $=p[l]$ $oxr$ $p[l+1]$ $...$ $p[r]$
即$l$ $oxr$ $(l+1)$ $...$ $r$ $oxr$ $p[l]$ $oxr$ $p[l+1]$ $...$ $p[r]=0$
问题等价于求异或和为$0$的子区间数量
------------
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=1e6+5;
mt19937_64 rng(time(0));
int n,p[M];
ll haxi[M];
unordered_map<ll,int> mp;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&p[i]);
ll tmp=rng();
haxi[p[i]]^=tmp;
haxi[i]^=tmp;
}
for(int i=1;i<=n;i++)haxi[i]^=haxi[i-1];
ll ans=0;
for(int i=0;i<=n;i++)
{
ans+=mp[haxi[i]];
mp[haxi[i]]++;
}
printf("%lld\n",ans);
return 0;
}
```