BZOJ4361: isn

-------------------------------------------------
 

[CQOI2015]任务查询系统

 
啊...我的程序跑了足足15s...真是弱爆了。很好奇第一名1K+的代码量1s是怎么做到的...
总之我的作法就是对时间维护一个树状数组套权值线段树。
这里有一个树状数组的妙用,传统的树状数组是单点修改,区间询问。这里我们把它变成区间修改,单点询问,同样是利用元素的可加性:
直接把每次询问变成询问前缀,方法就是添加的时候只在左端点添加,并在右端点的后一个减去。
 
然后这样时间复杂度是O(n * log^2(m) + m * log^2(K))的...