NOIP 模拟 $12\; \text{简单的区间}$

题解

签到题

求区间和为 $k$ 的倍数的区间，我们可以转化为求左右两个端点，其前缀和相等

对于区间最大值，我们可以把其转化为一个值，它能向左，向右扩展的最远边界，一个单调栈即可

我们设一个值 $i$，它能扩展的左右边界分别为 $l_i,r_i$ 那么我们将 $l_i～r_i$ 分为两部分，$l_i～i$，$i～r_i$

枚举较小的那一段（可以证明总复杂度为 $\mathcal O(nlogn)$ ），在另一段寻找前缀和等于此前缀和加 $num_i$ 的个数，用一颗动态开点线段树即可

注意：此种做法边界要卡得很细致

Code:

#include<bits/stdc++.h>

#define ri register signed

#define p(i) ++i

using namespace std;

namespace IO{

    char buf[1<<21],*p1=buf,*p2=buf;

    #define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++

    template<typename T>inline void read(T &x) {

        ri f=1;x=0;register char ch=gc();

        while(ch<'0'||ch>'9') {if (ch=='-') f=0;ch=gc();}

        while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}

        x=f?x:-x;

    }

}

using IO::read;

namespace nanfeng{

    #define cmax(x,y) ((x)>(y)?(x):(y))

    #define cmin(x,y) ((x)>(y)?(y):(x))

    #define FI FILE *IN

    #define FO FILE *OUT

    static const int N=3e5+7,K=1e6+1;

    int num[N],r[N],l[N],st[N],sum[N],nm[N],ans,tp,n,k;

    struct Segmenttree{

        #define ls(x) T[x].l

        #define rs(x) T[x].r

        #define up(x) T[x].nm=T[ls(x)].nm+T[rs(x)].nm

        struct seg{int l,r,nm;}T[K*20];

        int rt[K],tot;

        void update(int &x,int p,int l,int r) {

            if (!x) x=p(tot);

            if (l==r) {p(T[x].nm);return;}

            int mid(l+r>>1);

            if (p<=mid) update(ls(x),p,l,mid);

            else update(rs(x),p,mid+1,r);

            up(x);

        }

        int query(int x,int l,int r,int lt,int rt) {

            if (!x) return 0;

            if (l<=lt&&rt<=r) return T[x].nm;

            int mid(lt+rt>>1),res(0);

            if (l<=mid) res+=query(ls(x),l,r,lt,mid);

            if (r>mid) res+=query(rs(x),l,r,mid+1,rt);

            return res;

        }

    }T;

    inline int main() {

        // FI=freopen("nanfeng.in","r",stdin);

        // FO=freopen("nanfeng.out","w",stdout);

        read(n),read(k);

        for (ri i(1);i<=n;p(i)) {

            read(nm[i]);num[i]=nm[i]%k;

            sum[i]=(sum[i-1]+num[i])%k;

            T.update(T.rt[sum[i]],i,1,n);

            while(tp&&nm[st[tp]]<=nm[i]) r[st[tp--]]=i-1;

            l[i]=st[tp]+1;

            st[p(tp)]=i;

        }

        while(tp) r[st[tp--]]=n;

        for (ri i(1);i<=n;p(i)) {

            if (i==l[i]&&i==r[i]) continue;

            if (i-l[i]<=r[i]-i) {

                for (ri j(l[i]);j<i;p(j))

                    ans+=T.query(T.rt[(sum[j-1]+num[i])%k],i,r[i],1,n);

                if (i<r[i]) ans+=T.query(T.rt[sum[i]],i+1,r[i],1,n);

            } else {

                for (ri j(i+1);j<=r[i];p(j))

                    if (l[i]-1) ans+=T.query(T.rt[(sum[j]-num[i]+k)%k],l[i]-1,i-1,1,n);

                    else {

                        ri tmp=(sum[j]-num[i]+k)%k;

                        ans+=T.query(T.rt[tmp],l[i],i-1,1,n);

                        if (!tmp) p(ans);

                    }

                if (l[i]-1) ans+=T.query(T.rt[sum[i-1]],l[i]-1,i-2,1,n);

                else {

                    if (i-2) ans+=T.query(T.rt[sum[i-1]],1,i-2,1,n);

                    if (!sum[i-1]) p(ans);

                }

            }

        }

        printf("%d\n",ans);

        return 0;

    }

}

int main() {return nanfeng::main();}

官方题解做法，为 $\mathcal O(nlogn)$ 复杂度较优，但其实没什么太大区别

巴特西

NOIP 模拟 $12\; \text{简单的区间}$

题解

最新文章

热门文章