How to AK NOI online2022-senior

· · 个人记录

前言：

15+30+10=55pts，没进入前 25%，我是垃圾

T1-Stack

题目解法：

对于每一个成功的二元组，把它称为关键点（套用官方题解原话）。
然后观察一下可以发现，对于每一个二元组，都有一个区间 [l,r]，使其在这个区间中是关键点。可以对于每一个二元组，把最小的，满足其在区间 [l,r] 中是关键点的 l 求出来，记为 p_i。而它的 r 是多少都可行，就记为 n。这样最后询问时，答案就是询问区间 [l,r] 中满足 \forall{i} \in [l,r],p_i \le l 的数量。
显然，p 数组可以 O(n) 预处理。
然后，从 1 到 n 枚举端点，依次将 p_i 加入树状数组。如果当前点是某一组询问的左端点，当前点为 i，记当前小于等于 i 的点的数量为 sum(i)，那么这组询问的答案减去 sum(i)，因为最后要求的是 [l,r] 这个区间，所以先把 sum(i)（也就是区间 [1,l-1] 的答案）减去。如果当前点是某一组询问的右端点，记这组询问的左端点为 left，当前小于等于 left 的点的数量为 sum(left)，这组询问的答案加上 sum(left)（就是区间 [1,r] 的答案），因为区间 [1,l-1] 的答案已经提前减去了，所以现在的答案就是区间 [l,r] 的答案。

注意：

  1. 一定要枚举到第 i 个顶点时才把 p_i 加入树状数组，不然会导致错误的统计了 i+1 往后的顶点的答案。
  2. 一定要先删除多余的答案之后再把 p_i 加入树状数组，不然会错误的减去 p_i对答案的贡献。

\color{green}\text{AC 代码：}

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    inline int read()
    {
        int x=0,f=1;
        char ch=getchar();
        while(!isdigit(ch))
        {
            if(ch=='-')f=-1;
            ch=getchar();
        }
        while(isdigit(ch))
        {
            x=(x<<1)+(x<<3)+(ch^48);
            ch=getchar();
        }
        return x*f;
    }
    inline void write(int x)
    {
        if(x<0)putchar('-');
        if(x>=10)
            write(x/10);
        putchar(x%10^48);
    }
    const int maxn=5e5+5;
    int n,q;
    int a[maxn];
    int b[maxn];
    int p[maxn];
    int sta[maxn];
    int top;
    int tre[maxn<<2];
    vector<int> left[maxn];
    vector<int> right[maxn];
    int given_l[maxn];//每组询问的l
    int ans[maxn];
    inline int lowbit(int x)
    {
        return x&-x;
    }
    inline void add(int x,int val)
    {
        while(x<=n)
        {
            tre[x]+=val;
            x+=lowbit(x);
        }
    }
    inline int sum(int x)
    {
        int res=0;
        while(x>0)
        {
            res+=tre[x];
            x-=lowbit(x);
        }
        return res;
    }
    int main()
    {
        n=read();
        q=read();
        for(int i=1;i<=n;i++)
        {
            a[i]=read();
        }
        for(int i=1;i<=n;i++)
        {
            b[i]=read();
        }
        for(int i=1;i<=n;i++)
        {
            p[i]=1;
        }
        for(int i=n;i>=1;i--)
        {
            while((b[i]>b[sta[top]]&&(a[i]!=a[sta[top]]))&&top)
            {
                p[sta[top]]=i+1;
                top--;
            }
            sta[++top]=i;
        }
        int li,ri;
        for(int i=1;i<=q;i++)
        {
            li=read();
            ri=read();
            left[li].emplace_back(i);
            right[ri].emplace_back(i);
            given_l[i]=li;
        }
        for(int i=1;i<=n;i++)
        {//枚举端点
            for(int j=0;j<left[i].size();j++)
            {
                ans[left[i][j]]-=sum(i);
            }
            add(p[i],1);
            for(int j=0;j<right[i].size();j++)
            {
                ans[right[i][j]]+=sum(given_l[right[i][j]]);
            }
        }
        for(int i=1;i<=q;i++)
        {
            write(ans[i]);
            putchar('\n');
        }
        #ifndef ONLINE_JUDGE
        system("pause");
        #endif
        return 0;
    }
}
int main()
{
    Main::main();
    return 0;
}

T2 -Discuss

咕咕咕

T3 -Sort

咕咕咕