丹钓战

xieyikai2333 · 2022-03-26 13:14:37 · 题解

• 题目传送门

思路分析

• 既然题目叫做丹钓战，当然是用 单调栈（谐音梗，扣钱！） 树状数组做。

具体做法

对于每组数据：

1. 读入，将询问存入数组并记录询问编号；

2. 对询问按右端点从小到大排序：

3. 将 n 个二元组的编号依次加入题目所述的单调栈，记加入第 i 个二元组时栈顶元素为 t_i ，则当左端点在区间 [t_i+1,i] 中且右端点不小于 i 时第 i 个二元组对答案有贡献（请自行思考原因），所以对区间 [t_i+1,i] 中的每一个数加 1。当右端点为 i 时，询问的答案即为当前左端点对应的值。区间修改单点查询可以用树状数组维护；

代码实现

AC 代码：

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int l,r,id;
    bool operator < (const node &x)const
    {
        return this->r<x.r;
    }
}Q[500005];
int a[500005],b[500005],c[500005],ans[500005],n;
stack<int> stk;
int read()
{
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x;
}
void write(int x,int flag)
{
    if(!x)
    {
        if(flag)putchar('0');
        return;
    }
    write(x/10,false);
    putchar(x%10+'0');
    return;
}
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int v)
{
    for(int i=x;i<=n;i+=lowbit(i))c[i]+=v;
    return;
}
int sum(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i))res+=c[i];
    return res;
}
int main()
{
//  freopen("stack.in","r",stdin);
//  freopen("stack.out","w",stdout);
    int q,pos=1;
    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<=q;i++)Q[i].l=read(),Q[i].r=read(),Q[i].id=i;
    sort(Q+1,Q+q+1);
    a[0]=b[0]=INT_MAX;
    stk.push(0);
    for(int i=1;i<=n;i++)
    {
        while(true)
        {
            int j=stk.top();
            if(a[i]!=a[j]&&b[i]<b[j])break;
            stk.pop();
        }
        add(stk.top()+1,1),add(i+1,-1);
        stk.push(i);
        while(Q[pos].r==i)ans[Q[pos].id]=sum(Q[pos].l),pos++;
    }
    for(int i=1;i<=q;i++)write(ans[i],true),putchar('\n');
    return 0;
}