bzoj3333

题目不难……观察出某个性质就可以方便地做到O(nlgn)啊……
但是为毛线!!这么多人!!!O(nq)暴力过了!!!
为毛线!!!我O(nlgn)被卡常数了!!!!
哭了……

叫你不写zkw ——主席

题目比较复杂……就不概括了……我们看原题吧——排队计划
设序列第i个元素为a[i]
观察一些性质……容易发现:
如果我们记bi为所有满足j>i&&a[j]< a[i]的数字个数
那么一次操作后(不妨设该操作施加在pos_x)上
那么所有i< pos_x的bi都 不变
所有i>pos_x并且a[j]>a[i]的数字的bi都 不变
其它的bi都 赋值为0
正确性显然
当前序列的逆序对显然就是所有bi的和……

那么接下来问题抽象成以下模型

一个数列,数列每个元素有两个属性a,b
支持以下操作:
每次给定i……
将所有满足j>=i的且aj<=ai的bj求和……
然后立刻将所有满足j>=i的且aj<=ai的bj赋值为0

这个看起来可做多了……
考虑怎么用平衡树做到O(nlgn)

对序列建立一个平衡树
我们的关键字是position……
然后对于每个节点记录这个节点代表的子区间[l,r]的A的最小值,以及这个最小值对应的位置
那么我们每次询问[pos_x,n]的最小值,如果最小值小于等于a_pos_x
那么答案加上这个……然后把这个节点删掉就可以了
接下来继续询问最值……直到最小值比a_pos_x大或者不存在

由于一个节点最多被删1次……所以就nlgn了……
然后很容易推广到线段树怎么做……个人觉得平衡树比较好描述所以就讲了这个……

我愉悦地写了一个普通线段树……各种tle……
把询问和修改写一起了就过了……wtf!!

以上……那个结论是很显然的……但是为啥这么多人都交暴力……

Question:

  1. 暴力能过是因为这题暴力的理论复杂度上界比较低吗?
  2. 给定一个序列,每个元素有两个属性a,b,要求支持:

     将[l,r]区间中所有ai<=Query_v的i的b_i赋值为Change_v
     询问[l,r]区间中所有b_i的和
    

    这个不分块怎么做?

Comments

comments powered by Disqus