牛客训练(BIT+高精度)

又是这类用BIT辅助计数的题。。

这个显然满足要求的区间比不满足的要多太多，所以变成求不满足的。。。

然后要先求总方案数，为

这个不是很想在化了，反正O(n)求也可以的。。

然后求不满足的。。这里已经有4个端点，如果再枚举端点什么的显然很不明智。。因此应该从区间的性质入手，所以要枚举最值。。

枚举[l2,r2]的max，从大到小枚举，设此时的位置为i，可以发现，能构成区间2的个数有(i-pre[i])*(next[i]-i)，其中pre和next代表比a[i]大且里i最近的左边的数和右边的数。。此时有发现，其实区间1已经被pre[i]分隔开了，因为pre[i]后面的数区间1是绝对不能取的(否则区间1的min会小于区间2的max)，然后现在就是算区间1的个数了，可以发现区间1必须完全由之前被枚举过的数构成，那么只要用BIT维护一下i之前的这些区间块的个数和大小就可以了。。

这个要如何维护呢？每次枚举的时候判断一下左右是否被枚举过，如果有直接合并，把区间1的方案数修改一下即可。。

然后pre是用BIT算的，貌似有点浪费。。

另外总方案数会爆ll，之前学杜教的小高精终于能派上用场了。。

/**
 *　　　　　　　　┏┓　　 　┏┓
 * 　　　　　　　┏┛┗━━━━━━━┛┗━━━┓
 * 　　　　　　　┃　　　　　　　┃ 　
 * 　　　　　　　┃　　　━　　 　┃
 * 　　　　　　　┃　＞　　　＜　┃
 * 　　　　　　　┃　　　　　　　┃
 * 　　　　　　　┃...　⌒　... 　┃
 * 　　　　　　　┃　　　　　　　┃
 * 　　　　　　　┗━┓　　　┏━┛
 * 　　　　　　　　　┃　　　┃　Code is far away from bug with the animal protecting　　　　　　　　　　
 * 　　　　　　　　　┃　　　┃   神兽保佑,代码无bug
 * 　　　　　　　　　┃　　　┃　　　　　　　　　　　
 * 　　　　　　　　　┃　　　┃  　　　　　　
 * 　　　　　　　　　┃　　　┃
 * 　　　　　　　　　┃　　　┃　　　　　　　　　　　
 * 　　　　　　　　　┃　　　┗━━━┓
 * 　　　　　　　　　┃　　　　　　　┣┓
 * 　　　　　　　　　┃　　　　　　　┏┛
 * 　　　　　　　　　┗┓┓┏━┳┓┏┛
 * 　　　　　　　　　　┃┫┫　┃┫┫
 * 　　　　　　　　　　┗┻┛　┗┻┛
 */ 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<stdlib.h>
#include<assert.h>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define ll long long
#define eps 1e-8
#define succ(x) (1<<x)
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define mid (x+y)/2
#define NM 1000005 
#define nm 40005
#define pi 3.1415926535897931
const ll inf=1e16;
using namespace std;
ll read(){
    ll x=0,f=1;char ch=getchar() ;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}






int n,b[NM],nxt[NM],f[NM],sz[NM];
int c[NM];
ll a[NM];
__int128 ans;


void _add(int x,int t){for(;x<=n;x+=lowbit(x))c[x]=max(c[x],t);}
int _sum(int x,int s=0){for(;x;x-=lowbit(x))s=max(s,c[x]);return s;}
void add(int x,ll t){for(;x<=n;x+=lowbit(x))a[x]+=t;}
ll sum(int x,ll s=0){for(;x;x-=lowbit(x))s+=a[x];return s;}


int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
ll fun(ll n){return n*(n+1)/2;}

int main(){
    n=read();inc(i,1,n)b[read()]=i;
    inc(i,1,n+1)f[i]=i;
    nxt[0]=n+1;
    inc(i,1,n)ans+=(ll)i*(i-1)/2*(n-i+1);
    dec(k,n,1){
    int i=b[k];
    int l=_sum(i);int r=nxt[l];
    nxt[l]=i;nxt[i]=r;_add(i,i);
        __int128 s=(ll)(i-l)*(r-i);
    s*=sum(l);ans-=s;
    sz[i]=1;
    if(l==i-1){
        int x=find(l);
        sz[i]+=sz[x];f[x]=i;if(sz[x])add(x,-fun(sz[x]));
    }
    if(r==i+1){
        int x=find(r);
        sz[i]+=sz[x];f[x]=i;if(sz[x])add(x,-fun(sz[x]));
    }
    add(i,fun(sz[i]));
    }
    ll tmp;
    if(ans<inf)printf("%lld\n",tmp=ans);
    else{
    tmp=ans/inf;ll t=ans%inf;
    printf("%lld%016lld\n",tmp,t);
    }
    return 0;
}

链接：​​https://www.nowcoder.com/acm/contest/203/E​​​ 来源：牛客网
 

Trophies

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

输入描述:

第一行一个整数n (1 ≤ n ≤ 106)，第二行n个整数 (1 ≤ xi ≤ n)。

输出描述:

输出一行一个整数表示方案数。

示例1

输入

复制

51 4 3 5 2

输出

复制

28