【分治 / 玄學尺取】2019牛客暑期多校訓練營（第三場） - G - Removing Stones

題目連結https://ac.nowcoder.com/acm/contest/883/G

題意

給出n堆石子，每次可以從兩堆石子裡面各取出一個，如果能去光就獲勝。如果總數是奇數，可以先從任意一個最小堆選走一顆石子。問有多少個區間(l,r)，使得隻在這個區間内取石子，能獲勝。

題解一：

分治，複雜度 O ( N l o g 2 N ) O(Nlog^2N) O(Nlog2N)

直接上官方題解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+7;
int t,n,a[N];
int pos[N][33];
ll ans=0,sum[N];
int lg[N];
inline int getk(int l,int r){
    int f=lg[r-l+1];
    if(a[pos[l][f]]>a[pos[r-(1<<f)+1][f]]) return pos[l][f];
    else return pos[r-(1<<f)+1][f];
}
void dfs(int l,int r){
    if(l>=r) return;
    int k=getk(l,r);
    if(r-k<k-l){
        for(int i=r;i>=k;i--){
            if(sum[i]-sum[l-1]<2ll*a[k]) break;
            int lo=l,hi=k,p=0;
            while(lo<=hi){
                int mid=lo+hi>>1;
                if(sum[i]-sum[mid-1]>=2ll*a[k]) lo=mid+1,p=mid;
                else hi=mid-1;
            }
            ans+=p-l+1;
        }
    }
    else{
        for(int i=l;i<=k;i++){
            if(sum[r]-sum[i-1]<2ll*a[k]) break;
            int lo=k,hi=r,p=0;
            while(lo<=hi){
                int mid=lo+hi>>1;
                if(sum[mid]-sum[i-1]>=2ll*a[k]) hi=mid-1,p=mid;
                else lo=mid+1;
            }
            ans+=r-p+1;
        }
    }
    dfs(l,k-1);
    dfs(k+1,r);
}
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int _read(){
    char ch=nc();int sum=0;
    while(!(ch>='0'&&ch<='9'))ch=nc();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    return sum;
}
int main(){
    for(int i=1;i<N;i++) lg[i]=log2(i);
    t=_read();
    while(t--){
        ans=0;
        n=_read();
        for(int i=1;i<=n;i++){
            a[i]=_read();
            sum[i]=sum[i-1]+a[i];
            pos[i][0]=i;
        }
        for(int j=1;(1<<j)<=n;j++){
            for(int i=1;i+(1<<j)-1<=n;i++){
                if(a[pos[i][j-1]]>a[pos[i+(1<<j-1)][j-1]]) pos[i][j]=pos[i][j-1];
                else pos[i][j]=pos[i+(1<<j-1)][j-1];
            }
        }
        dfs(1,n);
        printf("%lld\n",ans);
    }
}


           

題解二

尺取，複雜度玄學

總共有 C n 2 C_n^2 Cn2​種區間，減去不符合條件的就是答案。

對于每個點，假設它是最大值，左端點往左移，然後右端點尺取的往右移。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+7;
int a[N];
int t,n;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        ll ans=1ll*n*(n-1)/2;
        for(int i=1;i<=n;i++){
            ll sum=0;
            int l=i,r=i;
            while(l>1&&sum+a[l-1]<a[i]){
                l--;sum+=a[l];
            }
            if(l<i) ans-=i-l;
            while(l<=i&&r<n){
                while(l<i&&sum+a[r+1]>=a[i]) sum-=a[l],l++;
                if(sum+a[r+1]>=a[i]) break;
                r++;sum+=a[r];
                ans-=i-l+1;
            }
        }
        printf("%lld\n",ans);
    }
}