繁华模拟赛day8 牛栏

/*

标称并没有用到题解中提到的那种奇妙的性质，我们可以证明，正常从1开始走的话，需要T次，如何使这个次数减小？题解中提到一个办法，有一步小于n/t，我们考虑这一步，如果把它匀到左右两步中，则可以减小，就根据这个性质来优化

next函数的部分，我当时用了一个倍增法，题解用了一个并查集，倍增比较直观，然而并查集更为巧妙

*/

//my code

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<queue>

#define ll long long

using namespace std;

const int maxn = ;

int n,q,cnt,ct[maxn];

ll a[maxn],sum[maxn],ans;

ll read(){

    char ch=getchar();

    ll x=,f=;

    while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};

    while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};

    return x*f;

}

ll greedy(int u,ll t){

    ll tot = ,tmp = ;

    ll j,lg,tst,nt;

    for(int i = ;i <= n;i++){

        tmp++;

        if(a[u] + a[u+] > t || i == n){

        }else{

            lg = ;

            j = ;

            tot = ;

            while(lg>=){

                if(u+j<=n){

                    tst = sum[u+j]-sum[u-];

                    nt = u + j;

                }

                else{

                    tst = sum[n] - sum[u-] + sum[u+j-n];

                    nt = u + j - n;

                }

                if(tot + tst <= t){

                    i += j;

                    tot += tst - a[nt];

                    u = nt;

                    lg++;

                    j <<= ;

                }else{

                    lg--;

                    j >>= ;

                }

            }

        }

        u++;

        if(u > n) u = ;

        if(tmp >= ans) break;

    }

    return tmp;

}

void work(ll t){

    cnt = ;

    ans = maxn;

    ct[++cnt] = ;

    ll sum = a[];

    for(int i = n;i > ;i--){

        sum += a[i];

        if(sum > t) break;

        ct[++cnt] = i;

    }

    for(int i = ;i <= cnt;i++){

        ans = min(ans,greedy(ct[i],t));

    }

    cout<<ans<<endl;

}

int main(){

    freopen("stall.in","r",stdin);

    freopen("stall.out","w",stdout);

    n = read();

    q = read();

    for(int i = ;i <= n;i++){

        a[i] = read();

        sum[i] = sum[i-] + a[i];

    }

    ll b;

    for(int i = ;i <= q;i++){

        b = read();

        work(b);

    }

    return ;

}

//std

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

#include<queue>

#include<map>

#include<set>

#include<stack>

#include<cstdlib>

#include<string>

#include<bitset>

#define INF 1000000000

#define N 2000005

#define fi first

#define se second

#define debug(x) cout<<#x<<"="<<x<<endl

#define MP(x,y) make_pair(x,y)

using namespace std;

typedef long long LL;

typedef pair<int,int> pii;

LL a[N],s[N];

int to[N],fa[N],d[N];

int findr(int x)

{

    if(fa[x]==x)

        return x;

    else

    {

        int t=fa[x];

        fa[x]=findr(fa[x]);

        d[x]=d[x]+d[t];

        return fa[x];

    }

}

void Union(int x,int y)

{

    fa[x]=y;

    d[x]=;

}

int main()

{

    int size =  << ; // 256MB

    char *p = (char*)malloc(size) + size;

    __asm__("movl %0, %%esp\n" :: "r"(p));

    freopen("stall.in","r",stdin);

    freopen("stall.out","w",stdout);

    cin>>n>>q;

    for(i=;i<=n;i++)

        scanf("%I64d",&a[i]),a[i+n]=a[i];

    for(i=n*;i;i--)

        s[i]=s[i+]+a[i];

    while(q--)

    {

        ans=INF;

        cin>>m;

        memset(d,,sizeof(d));

        for(i=;i<=n;i++)

            fa[i]=i,fa[i+n]=i+n;

        for(j=n*,i=n*;i;i--)

        {

            while(s[i]-s[j+]>m) j--;

            to[i]=j+;

            //debug(to[i]);

        }

        //if(q==1) return 0;

        for(i=;i<=n;i++)

        {

            j=findr(i);

            while(to[j]<i+n)

            {

                k=to[j];

                Union(j,k);

                j=findr(k);

            }

            findr(i);

            ans=min(ans,d[i]);

        }

        cout<<ans+<<endl;

    }

    return ;

}

// davidlee1999WTK 2015/

// srO myk Orz

//ios::sync_with_stdio(false);