Codeforces Round #576 (Div. 2) D （线段树+lazy-tag & 模拟）
D. Welfare State
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
There is a country with n citizens. The i-th of them initially has ai money. The government strictly controls the wealth of its citizens. Whenever a citizen makes a purchase or earns some money, they must send a receipt to the social services mentioning the amount of money they currently have.
Sometimes the government makes payouts to the poor: all citizens who have strictly less money than x are paid accordingly so that after the payout they have exactly x money. In this case the citizens don’t send a receipt.
You know the initial wealth of every citizen and the log of all events: receipts and payouts. Restore the amount of money each citizen has after all events.
Input
The first line contains a single integer n (1≤n≤2⋅105) — the numer of citizens.
The next line contains n integers a1, a2, …, an (0≤ai≤109) — the initial balances of citizens.
The next line contains a single integer q (1≤q≤2⋅105) — the number of events.
Each of the next q lines contains a single event. The events are given in chronological order.
Each event is described as either 1 p x (1≤p≤n, 0≤x≤109), or 2 x (0≤x≤109). In the first case we have a receipt that the balance of the p-th person becomes equal to x. In the second case we have a payoff with parameter x.
Output
Print n integers — the balances of all citizens after all events.
Examples
inputCopy
4
1 2 3 4
3
2 3
1 2 2
2 1
outputCopy
3 2 3 4
inputCopy
5
3 50 2 1 10
3
1 2 0
2 8
1 3 20
outputCopy
8 8 20 8 10
Note
In the first example the balances change as follows: 1 2 3 4 → 3 3 3 4 → 3 2 3 4 → 3 2 3 4
In the second example the balances change as follows: 3 50 2 1 10 → 3 0 2 1 10 → 8 8 8 8 10 → 8 8 20 8 10
题意 ：
给出n个数 有两种操作
1.将第 i个数变为 b
2.将低于b的数变为b
输出m次操作后的 这n个数分别是多少。
有两种做法：
方法一： 很容易看出可以使用线段树来做，1操作是单点更新，2操作设置lazy-tag当要对区间进行变化的时候再进行更新。
#include<bits/stdc++.h>
using namespace std;
const int N = 500500;
struct Tree
{
int tag,value;
};
Tree t[N<<2];
int a[N];
void Update(int rt)
{
t[rt].value = max(t[rt<<1].value,t[rt<<1|1].value);
}
void build(int l,int r,int rt)
{
t[rt].tag=0;
if(l==r)
{
t[rt].value = a[l];
return;
}
build(l,(l+r)>>1,rt<<1);
build((l+r)>>1|1,r,rt<<1|1);
Update(rt);
}
void Update2(int rt)
{
if(t[rt].tag)
{
int add = t[rt].tag;
t[rt<<1].tag = max(t[rt<<1].tag,add);
t[rt<<1|1].tag = max(t[rt<<1|1].tag,add);
t[rt].tag = 0;
}
}
void change(int p,int add,int l,int r,int rt)
{
if(l==r)
{
t[rt].value = add;
return;
}
Update2(rt);
int mid = (l+r)>>1;
if(p<=mid)
change(p,add,l,mid,rt<<1);
else
change(p,add,mid+1,r,rt<<1|1);
Update(rt);
}
int query(int p,int l,int r,int rt)
{
if(l==r)
{
return t[rt].value;
}
Update2(rt);
int mid = (l+r)>>1;
if(p<=mid)
query(p,l,mid,rt<<1);
else
query(p,mid+1,r,rt<<1|1);
Update(rt);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build(1,n,1);
int m;
scanf("%d",&m);
for(int i=0;i<m;i++)
{
int q;
scanf("%d",&q);
if(q==1)
{
int a,b;
scanf("%d%d",&a,&b);
change(a,b,1,n,1);
}
else
{
int a;
scanf("%d",&a);
t[1].tag = max(t[1].tag,a);
t[1].value = max(t[1].value,a);
}
}
for(int i=1;i<=n;i++)
{
printf("%d",query(i,1,n,1));
if(i==n)
printf("\n");
else
printf(" ");
}
}
方法二： 因为操作2是会被后到操作1或者是比它大的操作2所覆盖的，因此可以将所有进行过操作1的位置标记出来，然后逆序找出每个位置操作2所得到的最大值，比较它们取最大值。
#include<bits/stdc++.h>
using namespace std;
#define N 500000
int peo[N];
int vis[N];
int change[N];
int main()
{
int n;
scanf("%d",&n);
memset(vis,-1,sizeof(vis));
memset(change,-1,sizeof(change));
for(int i=0;i<n;i++)
scanf("%d",&peo[i]);
int m;
scanf("%d",&m);
for(int i=0;i<m;i++)
{
int q;
scanf("%d",&q);
if(q==1)
{
int a,b;
scanf("%d%d",&a,&b);
peo[a-1]=b;
vis[a-1]=i;
}
else
{
int a;
scanf("%d",&a);
change[i]=a;
}
}
int maxx = -1;
for(int i=m-1;i>=0;i--)
{
change[i] = max(maxx,change[i]);
maxx = change[i];
}
for(int i=0;i<n;i++)
{
if(vis[i]==-1)
printf("%d",max(peo[i],change[0]));
else
printf("%d",max(peo[i],change[vis[i]]));
if(i==n-1)
printf("\n");
else
printf(" ");
}
}