CF1614E题解

Tyyyyyy · 2021-12-03 15:07:17 · 题解

CF1614E

题意简述

• 有 n 天，每天有一个温度 T_i。
• 设当天屋内的温度为 P，则在每天温度会发生如下变化：

• 每天有 k_i 个询问，问你如果第一天早上屋内的温度为 t_{i,j}，则到现在屋内的温度是多少。
• 强制在线。

分析

本题有一种线段树二分的做法，可以参见其他题解。

这里介绍另一种做法：直接用线段树维护原来温度在区间 [l,r] 时实际温度的最大值和最小值。

在更新一个 T_i 时，我们讨论当前节点维护的信息与 T_i 的关系。

假设 tree[rt].max<T_i：直接对 rt 维护的区间进行区间加 1 的操作即可。

假设 tree[rt].min>T_i：直接对 rt 维护的区间进行区间减 1 的操作即可。

假设 tree[rt].max=tree[rt].min=T_i：直接返回即可。

可以发现上述三种情况已经覆盖了所有节点。

所以我们直接动态开点，按上述方式维护即可。

Code：

#include<bits/stdc++.h>
using namespace std;
constexpr int mod=1e9+1; 
int n,tot;
struct SegmentTree
{
    int ls,rs,mx,mn,laz;
    #define ls(i) tree[i].ls
    #define rs(i) tree[i].rs
    #define mx(i) tree[i].mx
    #define mn(i) tree[i].mn
    #define laz(i) tree[i].laz
}tree[30000010];
inline int New(int mn,int mx){tree[++tot]=(SegmentTree){0,0,mx,mn,0};return tot;}
inline void pushup(int rt)
{
    mx(rt)=max(mx(ls(rt)),mx(rs(rt)));
    mn(rt)=min(mn(ls(rt)),mn(rs(rt)));
}
inline void pushdown(int rt)
{
    if(!laz(rt))return;
    int l=ls(rt),r=rs(rt);
    mx(l)+=laz(rt),mn(l)+=laz(rt),laz(l)+=laz(rt);
    mx(r)+=laz(rt),mn(r)+=laz(rt),laz(r)+=laz(rt);
    laz(rt)=0; 
}
inline void upd(int rt,int l,int r,int op)
{
    if(mx(rt)<op){mx(rt)++,mn(rt)++,laz(rt)++;return;}
    if(mn(rt)>op){mx(rt)--,mn(rt)--,laz(rt)--;return;}
    if(mx(rt)==op&&mn(rt)==op)return;
    int mid=(l+r)>>1;
    if(!ls(rt))ls(rt)=New(l,mid);
    if(!rs(rt))rs(rt)=New(mid+1,r);
    pushdown(rt);
    upd(ls(rt),l,mid,op),upd(rs(rt),mid+1,r,op);
    pushup(rt);
}
inline int query(int rt,int l,int r,int t)
{
    if(l==t&&r==t){return mx(rt);}
    int mid=(l+r)>>1;
    if(!ls(rt))ls(rt)=New(l,mid);
    if(!rs(rt))rs(rt)=New(mid+1,r);
    pushdown(rt);
    if(t<=mid)return query(ls(rt),l,mid,t);
    return query(rs(rt),mid+1,r,t);
}
template<typename T>inline void read(T &x) 
{
    x=0;int f=1;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    x*=f;
}
int main()
{
    read(n);
    int lst=0,rt=New(0,mod-1);
    while(n--)
    {
        int t,k,x;
        read(t);read(k);
        upd(1,0,mod-1,t);
        for(int i=1;i<=k;i++)
        {
            read(x);x=(x+lst)%mod;
            lst=query(1,0,mod-1,x);
            printf("%d\n",lst);
        }
    }
    return 0;
}