题解 P2391 【白雪皑皑】

木木！ · 2019-07-19 11:42:13 · 题解

思路是挂链+堆。

先循环出每一个修改点，然后挂链保存修改。具体做法是将[l,r,c]挂在链表l上，保存r，c就是节点编号。

然后在输出的时候，遍历每一条链表，插入堆中。在堆中每一次取c最大的修改，如果r小于i就弹出。

还有一个小优化，如果r确定，则c越大越好。所以可以同时存下每一个ri对应的最大c，减少插入操作。

#include <queue>
#include <cstdio>
using namespace std;

int beg[1000005];
int ri[10000005];
int nxt[10000005];
int qi[10000005];

int maxi[1000005];

int main()
{
    int n,m,p,q;
    scanf("%d%d%d%d",&n,&m,&p,&q);
    p %= n;
    q %= n;

    int l = q+1;
    int r = p+1;
    for(int i=1; i<=m; ++i)
    {
        l += p; //用+代替*，-代替%，减少常数
        r += q;

        if(l>n)
        {
            l -= n;
        }
        if(r>n)
        {
            r -= n;
        }

        if(l<r)
        {
            ri[i] = r;
            nxt[i] = beg[l];
            beg[l] = i;
        }
        else
        {
            ri[i] = l;
            nxt[i] = beg[r];
            beg[r] = i;
        }
    }

    priority_queue<pair<int,int> > pq;
    for(int i=1; i<=n; ++i)
    {
        while(!pq.empty() && pq.top().second<i)
        {
            pq.pop();
        }
        for(int p=beg[i]; p; p=nxt[p])
        {
            if(p > maxi[ri[p]]) //小优化
            {
                pq.push(make_pair(p,ri[p]));
                maxi[ri[p]] = p;
            }
        }

        if(!pq.empty())
        {
            printf("%d\n",pq.top().first);
        }
        else
        {
            printf("0\n");
        }
    }
}