P4585

不知名用户 · 2023-12-29 09:54:50 · 题解

前言：为什么好多题解用可持久化 Trie 或者离线下来处理。其实可以不用这么干啊。再喷一下出题人：每天以进货结束，差点以为天以任意事件结束。

如果只有一个商店怎么做？

如果没有购买时间限制，这就是一个 01trie 模板。

如果有，我们在遍历 trie 时顺便记录每个点所有子节点时间戳最大的是多少。

如果有商店，就对商店线段树分治即可。具体地，每个线段表示所有子节点商品价格的 trie。

所以为什么题解喜欢对时间分治（虽然线段树分治模板是时间分治）。这题时间和商品都是一个区间，都可以分治。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, X = 20;

int rt[N*4], idx, mt[N*400], tr[N*400][2];

void ins(int p, int t, int x)
{
    int i;
    for(i=X;~i;i--)
    {
        mt[p] = max(mt[p],t);
        if(!tr[p][(x>>i)&1]) tr[p][(x>>i)&1] = ++idx;
        p = tr[p][(x>>i)&1];
    }
    mt[p] = max(mt[p],t);
}
int task(int p, int t, int x)
{
    int i, ans = 0;
    for(i=X;~i;i--)
    {
        int y = ((x >> i) & 1) ^ 1;
        if(tr[p][y]&&mt[tr[p][y]]>=t) ans += 1 << i, p = tr[p][y];
        else p = tr[p][1-y];
    }
    return ans;
}
void build(int p, int l, int r)
{
    rt[p] = ++idx;
    if(l==r) return;
    build(p*2,l,(l+r)>>1);build(p*2+1,((l+r)>>1)+1,r);
}
void add(int p, int L, int R, int x, int y, int z)
{
    ins(rt[p],y,z);
    if(L==R) return;
    int mid = L + R >> 1;
    if(x<=mid) add(p*2,L,mid,x,y,z);else add(p*2+1,mid+1,R,x,y,z);
}
int ask(int p, int l, int r, int t, int x, int L, int R)
{
    if(l<=L&&R<=r) return task(rt[p],t,x);
    int mid = L + R >> 1, ans = 0;
    if(l<=mid) ans = max(ans,ask(p*2,l,r,t,x,L,mid));
    if(mid<r) ans = max(ans,ask(p*2+1,l,r,t,x,mid+1,R));
    return ans;
}
int main()
{
    int n, m, day = 1, a, i;
    cin>>n>>m;
    build(1,1,n);
    for(i=1;i<=n;i++) cin>>a, add(1,1,n,i,114514,a);
    while(m--)
    {
        int op, l, r, x, d;
        cin>>op>>l>>r;
        if(op==0) add(1,1,n,l,++day,r);
        else cin>>x>>d, cout<<ask(1,l,r,day-d+1,x,1,n)<<'\n';
    }
    return 0;
}