分块 – Tgotp-Blog

3720: Gty的妹子树

正解貌似很麻烦,我直接用分块搞了。。。

具体见代码。

c++代码如下:

 

3295: [Cqoi2011]动态逆序对

暂时待填坑。。。

cdq分治,按照时间 t 排序(逆向,化删除为插入,每次保证分成的两段x有序,然后两次查询更改后增加的逆序对个数

c++代码如下:

 

分块:洛谷数据80分

c++代码如下:[......]

Read more

2141: 排队

题目大意:

求出每次更改后当前序列的逆序对个数。

考虑每次更改只会有两个点变化,且变化的个数只会与两数之间的数有关。

考虑分块处理(当然可以树套树),对于当前点所在块暴力更新,对于中间的块维护树状数组求出比他大的以及比他小的数。solved

送上对拍程序:
[crayon-[......]

Read more