mark一下

没想到铜牌题复杂度+自己手敲区间修改&区间查询(没学过)+打铁..

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct vv{
    int t,x;
}w[N],c[N];

bool cmp(vv a,vv b)
{
    if(a.t==b.t)    return a.x>b.x;
    else            return a.t<b.t;
}

struct Tree{
    int l,r,mx;
}tr[N<<2];
//线段树存当前节点的左右端点,以及左右端点的mx.

int lazy[N<<2];//存下延缓更新的区间最大值.

void pushup(int u)//利用子节点信息来更新父节点.
{
    tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);
}

void pushdown(int u)//利用父亲节点的懒标记给子节点赋值.
{
    if(!lazy[u]) return;
    tr[u<<1].mx=max(tr[u<<1].mx,lazy[u]);
    lazy[u<<1]=max(lazy[u],lazy[u<<1]);
    tr[u<<1|1].mx=max(tr[u<<1|1].mx,lazy[u]);
    lazy[u<<1|1]=max(lazy[u],lazy[u<<1|1]);
    lazy[u]=0;
}

void build(int u,int l,int r)
{
    if(l==r)
    {
        tr[u].l=tr[u].r=l;
        tr[u].mx=0;
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

void modify(int u,int l,int r,int L,int R,int val)//在根节点为u管辖区间[l,r]的时候找[L,R]更新max.
{
    int mid=(l+r)>>1;
    if(L<=l&&R>=r)      { tr[u].mx=max(tr[u].mx,val); lazy[u]=max(lazy[u],val);return; }
    pushdown(u);
    if(R<=mid)          modify(u<<1,l,mid,L,R,val);
    else if(L>=mid+1)   modify(u<<1|1,mid+1,r,L,R,val);
    else
    {
        modify(u<<1,l,mid,L,mid,val);
        modify(u<<1|1,mid+1,r,mid+1,R,val);
    }
    pushup(u);
}

int query(int u,int l,int r,int L,int R)//在根节点为u管辖区间[l,r]的时候找[L,R]的max.
{
    int mid=(l+r)>>1;
    if(L<=l&&R>=r)
    {
        return tr[u].mx;
    }
    pushdown(u);
    if(R<=mid)          return query(u<<1,l,mid,L,R);
    else if(L>=mid+1)   return query(u<<1|1,mid+1,r,L,R);
    else
    {
        int ans = 0;
        ans=max(ans,query(u<<1,l,mid,L,mid));
        ans=max(ans,query(u<<1|1,mid+1,r,mid+1,R));return ans;
    }
}

int main()
{
    int g=0,T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m,id=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=4*m;i++) lazy[i]=0;
        for(int i=1;i<=n;i++)   scanf("%d%d",&w[i].t,&w[i].x);//小周期和权值.
        sort(w+1,w+1+n,cmp);
        for(int i=1;i<=n;i++)
        {
            if(w[i].t!=w[i-1].t||i==1)    c[++id].t=w[i].t,c[id].x=w[i].x;
        }
        build(1,1,m);
        for(int i=1;i<=id;i++)
        {
            for(int j=1;j<=m;j+=(2*c[i].t))
            {
                modify(1,1,m,j,min(j+c[i].t-1,m),c[i].x);
            }
        }
        printf("Case #%d: ",++g);
        for(int i=1;i<=m;i++)
        {
            if(i!=m) printf("%d ",query(1,1,m,i,i));
            else     printf("%d",query(1,1,m,i,i));
        }puts("");
    }
    return 0;
}