题解 P1314 【聪明的质监员】

· · 题解

发一个特别的题解，给大家扩展一下思路。

本方法仅供参考，因为跑得很慢，非常慢。

此题我定睛一看，求区间大于W的个数以及大于W的元素的权值和，这不是经典的主席树题吗？

我们维护两个主席树，第一个主席树存储前i个元素中大于W的元素个数，第二个主席树存储前i个元素中大于W的元素的权值和。

这样我们用第j个主席树减第i-1个主席树，然后乘起来就可以得到区间[i, j]的Y了。

也就是说，现在我们只要有了W，就可以求得Y。

我们可以发现，W越大，每一个区间大于W的元素一定越少，同时权值和也跟着越少，即W越大，Y越小。

那么我们二分出一个W（二分范围：1~max(wi)+1），计算出Y。

如果Y==S，直接输出0；

如果Y>S，枚举更大的W，这样可以使Y小一些；

如果Y<S枚举更小的W，使Y大一些。

和一般的二分不同的是无论Y和S哪个大，都要更新一下答案。

注意一下：

0 < wi, vi≤10^6，要开long long，同时要离散化。

然后我交了一下， 3192ms！吓得我赶紧把离散化中的lower_bound改成了哈希，然后把动态分配内存改成了内存池， 2704ms 。

代码如下：

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
inline long long Read()
{
    long long i = 0, w = 1; char ch = 0;
    while (ch > '9' || ch < '0')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        i = i * 10 + ch - '0';
        ch = getchar();
    }
    return i * w;
}
#define HASH_SIZE    3214567
#define RAM_SIZE    2400010
// 内存池 
void * GetMemory(int iSize)
{
    static char arrMem[RAM_SIZE];
    static char * pTmpMem = arrMem;
    static int iMemTop;
    char * pAns = &pTmpMem[iMemTop];
    iMemTop += iSize;
    return pAns;
}
// 哈希 
struct SHashNode {
    int iData, iIndex;
    SHashNode * pNext;
} * arrHash[HASH_SIZE];
void AddHash(int iData, int iIndex)
{
    int iHash = iData % HASH_SIZE;
    if (iHash < 0)
        iHash = -iHash;
    SHashNode * pTmp = arrHash[iHash];
    while (pTmp)
    {
        if (pTmp->iData == iData)
            return;
        pTmp = pTmp->pNext;
    }
    pTmp = (SHashNode *)GetMemory(sizeof(SHashNode));
    pTmp->iData = iData;
    pTmp->iIndex = iIndex;
    pTmp->pNext = arrHash[iHash];
    arrHash[iHash] = pTmp;
}
struct SNode {
    long long iData;
    int iLNode, iRNode;
} arrNode[200010 << 5]; int iNodeTop;
struct SArea {
    int iLeft, iRight;
} arrArea[200010];
// 矿石的个数、区间的个数和标准值
long long iNumTot, iAreaTot, iStd;
//  i 号矿石的重量 wi 和价值vi
int arrWeight[200010], arrValue[200010];
// 二分右端点 
int iMaxWeight;
// 两个主席树 
int arrChairNum[200010], arrChairValue[200010];
// 离散化 
int arrUnique[200010], iUnique;
// 在哈希中查找离散值 
int GetIndex(int x)
{
    int iHash = x % HASH_SIZE;
    if (iHash < 0)
        iHash = -iHash;
    SHashNode * pTmp = arrHash[iHash];
    while (pTmp)
    {
        if (pTmp->iData == x)
            return pTmp->iIndex;
        pTmp = pTmp->pNext;
    }
    return 0;
}
// 创建主席树根节点 
int CreateChair(int iBegin, int iEnd)
{
    int iNode = ++iNodeTop;
    if (iBegin == iEnd)
        return iNode;
    int iMid = (iBegin + iEnd) / 2;
    arrNode[iNode].iLNode = CreateChair(iBegin, iMid);
    arrNode[iNode].iRNode = CreateChair(iMid + 1, iEnd);
    return iNode;
}
// 更新主席树，iDelta为变化量 
// 对于第一个主席树，iDelta==1
// 对于第二个主席树，iDelta==vi 
int UpdateChair(int iBefNode, int iBegin, int iEnd, int iIndex, int iDelta)
{
    int iNode = ++iNodeTop;
    arrNode[iNode].iData = arrNode[iBefNode].iData + iDelta;
    if (iBegin == iEnd)
        return iNode;
    int iMid = (iBegin + iEnd) / 2;
    if (iIndex <= iMid)
    {
        arrNode[iNode].iLNode = UpdateChair(arrNode[iBefNode].iLNode, iBegin, iMid, iIndex, iDelta);
        arrNode[iNode].iRNode = arrNode[iBefNode].iRNode;
    }
    else
    {
        arrNode[iNode].iLNode = arrNode[iBefNode].iLNode;
        arrNode[iNode].iRNode = UpdateChair(arrNode[iBefNode].iRNode, iMid + 1, iEnd, iIndex, iDelta);
    }
    return iNode;
}
// 获取主席树和 
long long GetSum(int iBefNode, int iAftNode, int iLeft, int iRight, long long iM)
{
    if (arrUnique[iRight] < iM)
        return 0;
    if (arrUnique[iLeft] >= iM)
        return arrNode[iAftNode].iData - arrNode[iBefNode].iData;
    long long iAns = 0; int iMid = (iLeft + iRight) / 2;
    iAns += GetSum(arrNode[iBefNode].iLNode, arrNode[iAftNode].iLNode, iLeft, iMid, iM);
    iAns += GetSum(arrNode[iBefNode].iRNode, arrNode[iAftNode].iRNode, iMid + 1, iRight, iM);
    return iAns;
}
long long GetY(long long iM)
{
    long long iAns = 0;
    for (int i = 1; i <= iAreaTot; i++)
    {
        long long a = GetSum(arrChairNum[arrArea[i].iLeft - 1], arrChairNum[arrArea[i].iRight], 1, iUnique, iM);
        long long b = GetSum(arrChairValue[arrArea[i].iLeft - 1], arrChairValue[arrArea[i].iRight], 1, iUnique, iM);
        iAns += a * b;
    }
    return iAns;
}
int main()
{
    // 读入 
    iNumTot = Read();
    iAreaTot = Read();
    iStd = Read();
    for (int i = 1; i <= iNumTot; i++)
    {
        arrUnique[++iUnique] = arrWeight[i] = Read();
        iMaxWeight = max(iMaxWeight, arrWeight[i]);
        arrValue[i] = Read();
    }
    // 离散化 
    sort(arrUnique + 1, arrUnique + 1 + iUnique);
    iUnique = unique(arrUnique + 1, arrUnique + 1 + iUnique) - arrUnique;
    iUnique--;
    for (int i = 1; i <= iUnique; i++)
        AddHash(arrUnique[i], i);
    for (int i = 1; i <= iAreaTot; i++)
        arrArea[i] = (SArea) { Read(), Read() };
    // 准备主席树 
    arrChairNum[0] = CreateChair(1, iUnique);
    arrChairValue[0] = CreateChair(1, iUnique);
    for (int i = 1; i <= iNumTot; i++)
    {
        arrChairNum[i] = UpdateChair(arrChairNum[i - 1], 1, iUnique, GetIndex(arrWeight[i]), 1);
        arrChairValue[i] = UpdateChair(arrChairValue[i - 1], 1, iUnique, GetIndex(arrWeight[i]), arrValue[i]);
    }
    // 二分 
    long long iAns = 40000000000000LL;
    int iLeft = 1, iRight = iMaxWeight + 1, iMid;
    while (iLeft <= iRight)
    {
        iMid = (iLeft + iRight) / 2;
        long long iTmpY = GetY(iMid);
        iAns = min(abs(iStd - iTmpY), iAns);
        if (iTmpY < iStd)
            iRight = iMid - 1;
        else if (iTmpY > iStd)
            iLeft = iMid + 1;
        else
        {
            iAns = 0;
            break;
        }
    }
    printf("%lld", iAns);
    return 0;
}