题解 P9343 【一曲新词酒一杯】

· · 题解

题目描述

这道题要求我们通过 1、2 两种操作更新去维护一个初始全置 0 的序列，问在给定要求 m 的范围内最少多少次可以使得序列均非 0，否则输出 -1。

解题思路

相对法与线段树

我们不难发现，这道题如果用暴力模拟，复杂度来到了我们难以接受的 O(n m) 级别，这时我们肯定需要考虑在操作 2 上动动脑筋。

我们容易得出，以相对的视角去看待操作 2，它更像是将自己减去 1 后得到的结果，但是这样肯定和题目不符，是哪里错了呢？

再次观察，可以发现其实所要求贴的红纸至少所需的数量也随之更新了，也是减去了 1。因为我们是以相对的视角更新操作 2 的，这就导致如果不更新至少数量，我们其他的序列值相当于没有与至少数量拉开差距，即没有加上 1。

至此，我们便可以请出今天的主角了：线段树

这个数据结构可以以 O(\log n) 的复杂度修改单点数值并查询区间最值，完美契合本题要求，板子一套即可。总体时间复杂度为 O(n+m \log n)。

完结撒花~

献上蒟蒻的 AC 代码：

#include <bits/stdc++.h>
using namespace std;
const int N=2000010;

int k,n,m,key,x;
bool flag;//输出判定，我个人的用法 

struct node//经典区间线段树 
{
    int l,r;
    int dat;
}t[N*4];

void build(int p,int l,int r)//建树 
{
    t[p].l=l,t[p].r=r;
    if(l==r)
    {
        t[p].dat=0;
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].dat=min(t[p*2].dat,t[p*2+1].dat);
}

void change(int p,int x,int v)//单点更改 
{
    if(t[p].l==t[p].r)
    {
        t[p].dat+=v;
        return;
    }
    int mid=(t[p].l+t[p].r)/2;
    if(x<=mid) change(p*2,x,v);
    else change(p*2+1,x,v);
    t[p].dat=min(t[p*2].dat,t[p*2+1].dat);
}

int main()
{
    scanf("%d",&k);
    while(k--)
    {
        scanf("%d %d",&n,&m);
        build(1,1,n);
        flag=false;
        int line=1;//至少数量为1，即最小值必须大于等于这个数 
        for(int i=1;i<=m;i++)
        {
            scanf("%d %d",&key,&x);
            if(flag) continue;
            flag=true;
            switch(key)
            {
                case 1:
                    change(1,x,1);//自己加1 
                    if(t[1].dat<line) flag=false;
                    break;
                case 2:
                    change(1,x,-1);line--;//自己和至少所需数量减1 
                    if(t[1].dat<line) flag=false;
                    break;
            }
            if(flag) printf("%d\n",i);
        }
        if(!flag) printf("-1\n");
    }
    return 0;
}
//我自己是用t[1]直接查询1-n最值的，没有写区间查询函数。想了解的OIer可以自行查阅相关资料。