写这个题解的原因是发现自己写了很多sb错误导致分数 $300 \to 100$ 加上发现出题人输出$10^6$个数还不提供快速输出板子加上板子就能 $3s \to 1s$ 的神奇比赛体验就来写一下这个题解。(题目还是很水的。。)

题目链接

A

一棵树,点有点权,$1$ 号点为根。点 $i$ 的答案是从根到 $i$ 路径上点的权值组成的序列有多少个后缀最大值(维护一个单调不增的单调栈的大小),求每个点的答案。$n \leq 10^6$

首先链情况就是单调栈。

首先因为单调栈的复杂度是均摊的所以我们不能回溯,我们可以考虑对于点 $i$ 找到它的祖先中距离它最近的 $a_v \geq a_i$,答案就是 $ans_i = ans_v+1$。

我当时做这个东西直接用了倍增,然后 MLE 了。

想一想还有另一种做法:单调栈复杂度不对是因为一个点会改多个元素,我们不妨只让他改一个元素:我们很容易连向到操作树,我们每次二分到哪个位置,直接在这个位置后面连上这个点就好了。但是发现操作树是动态的并不能二分,那么我们可以直接把栈中对应的位置直接改掉,并且修改一下记录的栈顶,这样就不用花时间删除后面的元素了。最后回溯的时候再改回去即可。发现在每个点对栈的修改是 $O(1)$ 的,总复杂度 $O(n \log n)$。

但是这个题不加快速输出就 T 飞了,加上就会有 $0.015s$ 的好成绩。(怀疑是LemonLime测读入时间的锅)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define db double
#define U unsigned
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

#define ll long long
namespace FASTIO{
    const int S=(1<<23)+5;static char b[S],o[S],p[20],*H=b,*T=b,*O=o,*P;static int r,s,c;
    inline char gc(){return H==T?T=(H=b)+fread(b,1,S,stdin):0,H!=T?*H++:-1;}
    inline int rf(){s=0;for(;!isdigit(c=gc());s=c);
                    for(r=c^48;isdigit(c=gc());(r*=10)+=c^48);
                    return s^45?r:-r;}
    inline ll rfl(){ll r;s=0;for(;!isdigit(c=gc());s=c);
                    for(r=c^48;isdigit(c=gc());(r*=10)+=c^48);
                    return s^45?r:-r;}
    inline int ef(){return fwrite(o,1,O-o,stdout),O=o,0;}
    inline int w(){return O-o>S-128?ef():0;}
    inline void wf(int x,char e=10){for(x<0?*O++=45,x=-x:0,x?:*O++=48,P=p;x;*++P=x%10+48,x/=10);
                                    for(;P!=p;*O++=*P--);e?*O++=e,w():0;}
    inline void wfl(ll x,char e=10){for(x<0?*O++=45,x=-x:0,x?:*O++=48,P=p;x;*++P=x%10+48,x/=10);
                                    for(;P!=p;*O++=*P--);e?*O++=e,w():0;}
    inline void ws(const char *e){strcpy(O,e);O+=strlen(e);w();}
    inline void wc(char e){*O++=e;w();}
}
using FASTIO::rf;using FASTIO::rfl;using FASTIO::ef;
using FASTIO::wf;using FASTIO::wfl;using FASTIO::ws;using FASTIO::wc;

const int MAXN = 1e6 + 5;

std::vector<int> G[MAXN];

int n,a[MAXN];
int stk[MAXN],tp[MAXN];

inline void dfs(int v){
    int ps,bk;
    if(v == 1){
        stk[++tp[v]] = a[v];
    }
    else{
        int l = 1,r = tp[v],ans = 0;
        while(l <= r){
            int mid = (l + r) >> 1;
            if(stk[mid] >= a[v]) ans = mid,l = mid+1;
            else r = mid-1;
        }
        tp[v] = ans+1;
        ps = tp[v],bk = stk[ps];
        stk[ps] = a[v];
    }
    for(auto x:G[v]){
        tp[x] = tp[v];
        dfs(x);
    }
    if(v != 1) stk[ps] = bk;
}

int main(){
    freopen("suffix.in","r",stdin);
    freopen("suffix.out","w",stdout);
    n = rf();
    FOR(i,2,n){
        int f=rf();G[f].pb(i);
    }
    FOR(i,1,n) a[i] = rf();
    dfs(1);
    FOR(i,1,n) wf(tp[i],' ');wc('\n');ef();
    return 0;
}

B

长度为 $n$ 的序列 $a_i$,给定一个常数 $k$ ,问有多少个区间 $[l,r]$,满足 $\max_{i=l}^n\{a_i\} + \min_{i=l}^r \{a_i\} = k$。 $n \leq 10^6$。

经典题。分治,考虑跨过中点的所有区间,分类讨论最大值最小值在左边还是右边就好了。需要注意有多个最大值/最小值的时候要特判,我是强制最大值最小值在左边计算的。

这题感觉是全场最舒适的题了,不卡输出也没有写挂。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

inline char nc(){
    #define SIZE 1000000+3
    static char buf[SIZE],*p1 = buf+SIZE,*p2 = buf+SIZE;
    if(p1 == p2){
        p1 = buf;p2 = buf+fread(buf,1,SIZE,stdin);
        if(p1 == p2) return -1;
    }
    return *p1++;
    #undef SIZE
}

template <typename T>
inline void read(T &x){
    x = 0;int flag = 0;char ch = nc();
    while(!isdigit(ch)){
        if(ch == '-') flag = 1;
        ch = nc();
    }
    while(isdigit(ch)){
        x = (x<<1) + (x<<3) + (ch^'0');
        ch = nc();
    }
    if(flag) x = -x;
}

const int MAXN = 1e6 + 5;
int n,x,a[MAXN];
LL ans = 0;
int mx[MAXN],mn[MAXN];

inline void work(int l,int r){
    if(l > r) return;
    if(l == r){
        ans += (2*a[l]==x);
        return;
    }
    int mid = (l + r) >> 1;
    mx[mid] = -1e9;mn[mid] = 1e9;
    FOR(i,mid+1,r){
        mx[i] = std::max(mx[i-1],a[i]);
        mn[i] = std::min(mn[i-1],a[i]);
    }
    mx[mid] = a[mid];mn[mid] = a[mid];
    ROF(i,mid-1,l){
        mx[i] = std::max(mx[i+1],a[i]);
        mn[i] = std::min(mn[i+1],a[i]);
    }
    int i1=mid,i2=mid;// min/max
    ROF(i,mid,l){
        if(mx[i]+mn[i] != x) continue;
        while(i1 < r && mn[i1+1] >= mn[i]) i1++;
        while(i2 < r && mx[i2+1] <= mx[i]) i2++;
        ans += std::min(i1,i2)-mid;
    }
    i1 = mid+1,i2 = mid+1;
    FOR(i,mid+1,r){
        if(mx[i]+mn[i] != x) continue;
        while(i1 > l && mn[i1-1] > mn[i]) i1--;
        while(i2 > l && mx[i2-1] < mx[i]) i2--;
        ans += mid+1-std::max(i1,i2);
    }
    i2 = mid;int ll = mid+1,rr = mid;
    ROF(i,mid,l){
        while(i2 < r && mx[i2+1] <= mx[i]) i2++;
        int d = x-mx[i];
        if(d >= mn[i]) continue;
        while(rr < r && mn[rr+1] >= d) ++rr;
        if(rr == r && mn[rr] != d) break;
        while(ll <= r && mn[ll] > d) ++ll;
        if(ll <= rr && mn[ll] == d && mn[rr] == d) ans += std::max(0,std::min(rr,i2)-ll+1);
    }
    i1 = mid+1;ll = mid+1,rr = mid;
    FOR(i,mid+1,r){
        while(i1 > l && mx[i1-1] < mx[i]) i1--;
        int d = x-mx[i];
        if(d > mn[i]) continue;
        while(ll > l && mn[ll-1] >= d) --ll;
        if(ll == l && mn[ll] != d) break;
        while(rr >= l && mn[rr] > d) --rr;
        if(ll <= rr && mn[ll] == d && mn[rr] == d) ans += std::max(0,rr-std::max(i1,ll)+1);
    }
    work(l,mid);work(mid+1,r);
}

int main(){
    freopen("interval.in","r",stdin);
    freopen("interval.out","w",stdout);
    read(n);read(x);
    FOR(i,1,n) read(a[i]);
    work(1,n);
    printf("%lld\n",ans);
    return 0;
}

C

int B;
void init(int n)
{
    ans=0;
    for(int i=1;i<=n;i++)belong[i]=(i-1)/B+1;
}
void query(int l,int r)
{
    if(belong[l]==belong[r])
    {
        for(int i=l;i<=r;i++)++ans;
        return;
    }
    for(int i=belong[l]+1;i<belong[r];i++)++ans;
    int R=belong[l]*B,L=(belong[r]-1)*B+1;
    for(int i=L;i<=r;i++)++ans;
    for(int i=l;i<=R;i++)++ans;
}
int main()
{
    scanf("%d%d",&n,&m);init(n);
    for(int i=1,l,r;i<=m;i++)
    {
        scanf("%d%d",&l,&r);
        query(l,r);
    }
    cout<<ans<<endl;
}

问这段代码在 $B = 1\ldots n$ 输出的值。$n,m \leq 10^6$。

首先写一下式子:假设当前的块长是 $B$,我们考虑区间 $[l,r]$ 的答案:

如果 $r-l+1 \leq B$,答案是 $r-l+1$。

否则答案是

$$ (\lfloor \frac{r-1}{B}\rfloor -\lfloor \frac{l-1}{B}\rfloor)+((\lfloor \frac{l-1}{B}\rfloor +1)\cdot B-(l-1))+(r-1-\lfloor \frac{r-1}{B}\rfloor\cdot B) $$

整理一下式子

$$ (\lfloor \frac{r-1}{B}\rfloor\cdot (1-B)+r)-(\lfloor \frac{l-1}{B}\rfloor \cdot (1-B)+l)+B $$

所以我们设 $f(x) = \lfloor \frac{x-1}{B} \rfloor \cdot (1-B)+x$,那么一个区间的答案就是 $f(r)-f(l)+B$。

所以我们现在可以把每个区间拆成两个点,一个贡献为正一个贡献为负,现在我们只要考虑如何计算 $f$ 的和就行了。

首先我们去枚举 $B$,然后可以发现本质不同的 $\lfloor \frac{x}{B} \rfloor$ 只有 $\lfloor \frac{n}{B} \rfloor$ 种,所以总共就是 $O(n \log n)$ 种。

所以我们可以去枚举所有的取值,然后相当于询问区间和(左端点为 $-1$,右端点为 $1$),用树状数组维护即可。

然后我们要处理 $r-l+1 \leq B$ 的部分:我们枚举到指定长度后就直接把长度 $=B$ 的区间在树状数组的贡献删掉,然后对应维护一下答案增量就行了。时间复杂度 $O(n \log^2 n)$ 但是由于是树状数组和调和级数的 $\log$ 所以很不满。具体做的时候你可以倒序枚举 $B$ 减少一点常数(虽然好像没有啥用,复杂度瓶颈在于询问不在于修改)

但是我考试的时候把 $m$ 写成 $n$ 了加上对拍的时候默认 $m=n$ 就挂零了。。要不然就过了

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define db double
#define U unsigned
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e6 + 5;
#define ll long long
namespace FASTIO{
    const int S=(1<<23)+5;static char b[S],o[S],p[20],*H=b,*T=b,*O=o,*P;static int r,s,c;
    inline char gc(){return H==T?T=(H=b)+fread(b,1,S,stdin):0,H!=T?*H++:-1;}
    inline int rf(){s=0;for(;!isdigit(c=gc());s=c);
                    for(r=c^48;isdigit(c=gc());(r*=10)+=c^48);
                    return s^45?r:-r;}
    inline ll rfl(){ll r;s=0;for(;!isdigit(c=gc());s=c);
                    for(r=c^48;isdigit(c=gc());(r*=10)+=c^48);
                    return s^45?r:-r;}
    inline int ef(){return fwrite(o,1,O-o,stdout),O=o,0;}
    inline int w(){return O-o>S-128?ef():0;}
    inline void wf(int x,char e=10){for(x<0?*O++=45,x=-x:0,x?:*O++=48,P=p;x;*++P=x%10+48,x/=10);
                                    for(;P!=p;*O++=*P--);e?*O++=e,w():0;}
    inline void wfl(ll x,char e=10){for(x<0?*O++=45,x=-x:0,x?:*O++=48,P=p;x;*++P=x%10+48,x/=10);
                                    for(;P!=p;*O++=*P--);e?*O++=e,w():0;}
    inline void ws(const char *e){strcpy(O,e);O+=strlen(e);w();}
    inline void wc(char e){*O++=e;w();}
}
using FASTIO::rf;using FASTIO::rfl;using FASTIO::ef;
using FASTIO::wf;using FASTIO::wfl;using FASTIO::ws;using FASTIO::wc;

struct BIT{
    #define lowbit(x) ((x)&(-(x)))
    int tree[MAXN];

    inline void add(int pos,int x){
        pos += 2;
        while(pos < MAXN){
            tree[pos] += x;
            pos += lowbit(pos);
        }
    }

    inline int calc(int pos){
        int res = 0;pos += 2;
        while(pos){
            res += tree[pos];
            pos -= lowbit(pos);
        }
        return res;
    }

    inline int query(int l,int r){
        return calc(r)-calc(l-1);
    }
}bit;

int n,m;
std::vector<std::pair<int,int> > G[MAXN];

int main(){
    freopen("block.in","r",stdin);
    freopen("block.out","w",stdout);
//    read(n);read(m);
    n = rf();m = rf();
    LL smx = 0,cnt = 0,sm = 0;
    FOR(i,1,m){
        int l=rf(),r=rf();//read(l);read(r);
//        bit.add(r-1,1);bit.add(l-1,-1);
        G[r-l+1].pb(MP(l,r));
        sm += r-l+1;
    }
    // (1-b) (x-1)/B + x
    std::vector<LL> out;
    ROF(B,n,1){
        LL ans = sm+smx;
        for(int l = 0,r = B-1;l < n;l = r+1,r = l+B-1){
            r = std::min(r,n-1);
            ans += 1ll*(1-B)*(l/B)*bit.query(l,r);
        }
        ans += 1ll*cnt*B;
        out.pb(ans);
        FOR(i,0,(int)G[B].size()-1){
            auto x = G[B][i];
            sm -= x.se-x.fi+1;
            bit.add(x.se-1,1);
            bit.add(x.fi-1,-1);
            smx += x.se-x.fi;
            ++cnt;
        }
    }
    std::reverse(all(out));
    for(auto x:out) wfl(x,' ');wc('\n');ef();
    return 0;
}

总结

对拍的时候所有变量请随机。
输出 $10^6$ 个数的时候如果程序很慢请考虑是不是输出的问题,不要卡常浪费时间了。(Linux 看 user time,Windows自己手动time一下)

Last modification:September 2nd, 2020 at 09:37 pm
如果觉得我的文章对你有用,请随意赞赏