求助Re：9

傷城~ 2021-12-03 16:59 163阅读 0赞

![1708132-20190717092756242-1275048321.png][]

![1708132-20190717092653016-1677838875.png][]

--------------------

#include<bits/stdc++.h>
    #define ll long long
    #define A 1100000
    using namespace std;
    ll lmax[A],lmin[A],rmax[A],rmin[A],a[A],tong[A],n;
    ll work(ll l,ll r,ll mid){
        ll w=0;
        lmax[mid]=a[mid];lmin[mid]=a[mid];
        rmax[mid+1]=a[mid+1];rmin[mid+1]=a[mid+1];
        for(ll i=mid-1;i>=l;i--){
            lmax[i]=max(lmax[i+1],a[i]);
            lmin[i]=min(lmin[i+1],a[i]);
        }
        for(ll i=mid+2;i<=r;i++){
            rmax[i]=max(rmax[i-1],a[i]);
            rmin[i]=min(rmin[i-1],a[i]);
        }
        for(ll i=l;i<=mid;i++){
            ll j=i+lmax[i]-lmin[i];
            if(j>mid&&rmax[j]<lmax[i]&&rmin[j]>lmin[i]) w++;
        }
        ll p1=mid+1,p2=mid;
        while(p1<=r&&rmax[p1]<lmax[l]) tong[rmax[p1]-p1]--,p1++;
        while(p2<r&&rmin[p2+1]>lmin[l]) p2++,tong[rmax[p2]-p2]++;
        for(ll i=l;i<=mid;i++){
            while(p1>mid+1&&rmax[p1-1]>lmax[i]) p1--,tong[rmax[p1]-p1]++; 
            while(p2>mid&&rmin[p2]<lmin[i]) tong[rmax[p2]-p2]--,p2--;
            w+=max(tong[lmin[i]-i],0ll);
        }
        for(ll i=mid+1;i<=r;i++){
            tong[rmax[i]-i]=0;
        }
        return w;
    }
    ll solve(ll l,ll r){
        if(l==r) return 1;
        ll mid=(l+r)>>1;
        ll zz=solve(l,mid)+solve(mid+1,r);
        zz+=work(l,r,mid);
        reverse(a+l,a+r+1);
        if((r-l+1)&1) mid--;
        zz+=work(l,r,mid);
        reverse(a+l,a+r+1);
        return zz;
    }
    int main(){
        scanf("%lld",&n);
        for(ll i=1;i<=n;i++){
            ll xx,yy;
            scanf("%lld%lld",&xx,&yy);
            a[xx]=yy;
        }
        cout<<solve(1,n);
    }

把tong放在a前面就AC了，否则会RE

为什么

救我

开数组已经是100倍了，100000就够，我开了10000000都不行

转载于:https://www.cnblogs.com/znsbc-13/p/11198928.html

[1708132-20190717092756242-1275048321.png]: /images/20211203/d6ad859bfb694503be7c66aded3c4925.png
[1708132-20190717092653016-1677838875.png]: /images/20211203/0964af4be6d541d986ebb8aaeff693ca.png