[分治][mergesort][经典算法推广][实现] Codeforces Round #510 div2 D Petya and Array

http://codeforces.com/contest/1042/problem/D

嗯，大概是发现了自己以前一直没有正确理解mergesort。。。。

vp时候发现一开始这个题目过的人竟然比C多然后就提前去看了，但是竟然并没想出来正解emmmmmm，想过分治但是不知道怎么在线性合并左右段，看了前排dalao代码恍然大悟，其实就是逆序数的推广，这里把前缀和当成要处理的对象即可，如果是逆序数的话就是输出来一个数字右边有多少个比他大的，这里的话是sum[i]的右边有多少个比sum[i]+t小的，而t是常数所以其实几乎和逆序数一样。。如果仔细考虑逆序数的分治算法的话，会发现他能保证合并的时候线性是因为每次左右两边都是排好序的，这样的话就可以线性合并，而为什么排序这个操作不会影响到结果呢？因为在合并的时候左右两边各自的结果已经被计算过了，需要计算的仅仅是跨越中点的那些lr对！而这些计算和左右两边各自的顺序没有关系，只要保证左边的在左边右边的在右边就行了：因为我们是计算合法的数量，只要存在就+1，跟他什么时候存在早存在晚存在没关系。

实现细节的话，有点意思。这里需要处理的线段端点条件是很烦的，然而事实证明很烦只是自己写的太挫了。。。这里用的一直都是差分，然而要求l到r之间的和要么是sum[r]-sum[l-1]要么是sum[r+1]-sum[l]，但是这里在实现上使用了后者。。我一开始没有看懂为什么非要这么写，后来自己写了一遍才知道这么写有多少好处。首先这样处理的话可以不用特判线段长度为1的情况：只要每次都从右侧线段第一个节点开始考虑就行了，这么做的话递归起来只有最左侧的点不会被计算到但是在这里很妙的最左侧的是sum[0]，也就是所有sum的参考点，他是不需要计算到最后计数里的，但是需要参与到排序中去提供参考。另外，处理到每一段的时候，都不会计算这一段的最左侧节点为l的情况：这种情况留给了父节点去把它当成mid+1计算了。。而最后根节点的最左侧是sum[0]不用计算。。整个设计都很巧妙，很难说是本来就这么设计的还是偶然的巧合。。。用递归的思想看问题真的很重要

 

#include

using namespace std;

typedef long long LL;
const int maxn=2e5+100;
const int mod=1e9+7;

LL sum[maxn],n,t,ans;

void solve(int l,int r)
{

    if(l>=r)return ;
    int mid=(l+r)>>1;
    solve(l,mid);
    solve(mid+1,r);
    LL tmp=0;
    for(int i=l,j=mid;i<=mid;i++)
    {
        while(j>n>>t;
    for (int i=1;i<=n;i++)
        cin>>sum[i],sum[i]+=sum[i-1];
    solve(0,n);
    cout<