形式化题意第一行输入n,qn,qn,q空格分隔。初始有一个长度为nnn的序列满足∀i∈[1,n],aii\forall i\in[1,n],a_ii∀i∈[1,n],ai​i。现给出qqq组操作询问每次操作输入x,yx,yx,y数据保证xyxyxy表示操作op(x,y)\texttt{op(x,y)}op(x,y)∀i∈[1,n]\forall i\in[1,n]∀i∈[1,n]满足ai≤xa_i\leq xai​≤x输出iii的数量并执行ai←ya_i\gets yai​←y。数据范围1≤n≤106,1≤q≤1061\leq n \leq 10^6,1\leq q\leq 10^61≤n≤106,1≤q≤106。时限1s\text{1s}1s空间限制128MB\text{128MB}128MB。Solution 1看到这种区间修改/查询首先想到的应该是线段树。但是ai≤xa_i\leq xai​≤x非常难弄我们可以考虑计数。记cntxcnt_xcntx​为∀i∈[1,n]\forall i\in[1,n]∀i∈[1,n]满足aixa_ixai​x的个数。则输出ai≤xa_i\leq xai​≤x的数量显然可以变成∑i1xcnti\sum_{i1}^{x}cnt_ii1∑x​cnti​而把ai≤xa_i\leq xai​≤x全部修改为yyy可以这么做由于xyxyxy111到xxx中不会包含yyycnty←cnty∑i1xcnticnt_y\gets cnt_y\sum_{i1}^{x}cnt_icnty​←cnty​i1∑x​cnti​cnt1..x0cnt_{1..x}0cnt1..x​0区间查询区间修改显然可以用线段树维护于是解决了这个问题。时间复杂度O(nqlog⁡n)O(nq\log n)O(nqlogn)空间复杂度O(n)O(n)O(n)实际要开444倍空间。但是由于线段树有444的常数运算次数已经达到了7×1077\times 10^77×107左右所以该方法还是擦着时限过的有没有优化呢Solution 2还是要用到cntcntcnt。注意题目当中有一句话数据保证xyxyxy我们观察到初始时aiia_iiai​i而每次操作只有可能将aia_iai​变大而不会变小所以在执行了任何一次操作后所有iii满足ai≥ia_i\geq iai​≥i所以≤x\leq x≤x的aia_iai​只有可能在[1,x][1,x][1,x]中出现。假设之前执行了若干次操作而所有操作中最大的xxx设为XXX其对应的yyy设为YYY。假设这次执行的操作为op(x’,y’)\text{op(x,y)}op(x’,y’)。若x′≤Xx\leq Xx′≤X显然这个操作是没用的因为≤x′\leq x≤x′的数早就被更新为YYY了输出000后 continue 即可若x′XxXx′X因为显然a1..XXa_{1..X}Xa1..X​X≤X\leq X≤X的数已经变成YYY了只需要在[X1,x′][X1,x][X1,x′]暴力循环一遍即可。时间复杂度每个位置不会被重复遍历因此时间复杂度是O(nq)O(nq)O(nq)的空间复杂度O(n)O(n)O(n)。基本上没有什么常数因子。区赛 T3 改编。简单题我怎么80pts\text{80pts}80pts呢我问我自己。全区的人怎么也没做出来呢/caiji 半年前的我还是太菜了 /caiji