JZOJ4737. 【NOIP2016提高A组模拟8.25】金色丝线将瞬间一分为二

题解

很显然x的贡献跟y的贡献是互相独立的，
有一种思路，就是二分个答案，然后转化成判定性问题，
也就是只要在O(n)的时间里面统计好距离和就可以了。
用x来举例，y同理，
将x从小到大排序，并记录每个x是第几个x。
枚举i，记录在i前面有多少个x是在mid之前，以及它们的和。
显然，i这个位置的x就是前面的个数*xi$x_i$-前面x的和。

如果题目再加强一下，就是要输出每个尸体加入的时候的距离和。
其实做法也大致相同，就是用树状数组维护就可以了。

code

#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string.h>
#include <cmath>
#include <math.h>
#define ll long long
#define N 600003
#define M 103
#define P putchar
#define G getchar
using namespace std;
char ch;
void read(int &n)
{
    n=0;
    ch=G();
    while((ch<'0' || ch>'9') && ch!='-')ch=G();
    ll w=1;
    if(ch=='-')w=-1,ch=G();
    while('0'<=ch && ch<='9')n=(n<<3)+(n<<1)+ch-'0',ch=G();
    n*=w;
}

int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
ll abs(ll x){return x<0?-x:x;}
ll sqr(ll x){return x*x;}
void write(ll x){if(x>9) write(x/10);P(x%10+'0');}

ll sum,s[4][N],tx,ty,sx,sy,d,sumx,sumy;
int x[N],xx[N],y[N],yy[N],h[N],n;

int x_(int x){return x&(-x);}

ll find(int x,int z)
{
    ll S=0;
    for(int i=x;i;i=i-x_(i))
        S=S+s[z][i];
    return S;
}

void ins(int x,int y,int z)
{
    for(int i=x;i<=n;i=i+x_(i))
        s[z][i]=s[z][i]+y;
}

int main()
{
    freopen("find.in","r",stdin);
    freopen("find.out","w",stdout);

    scanf("%d%lld",&n,&d);
    for(int i=1;i<=n;i++)
        read(x[i]),read(y[i]);

    memcpy(h,x,sizeof(h));
    sort(h+1,h+1+n);
    for(int i=1;i<=n;i++)
        xx[i]=lower_bound(h+1,h+1+n,x[i])-h;

    memcpy(h,y,sizeof(h));
    sort(h+1,h+1+n);
    for(int i=1;i<=n;i++)
        yy[i]=lower_bound(h+1,h+1+n,y[i])-h;

    for(int i=1;i<=n;i++)
    {
        sx=find(xx[i],0);
        tx=find(xx[i],1);
        sy=find(yy[i],2);
        ty=find(yy[i],3);
        sum=sum+sumx-sx*2-(i-2*tx-1)*x[i];
        sum=sum+sumy-sy*2-(i-2*ty-1)*y[i];

        if(sum>d)
        {
            printf("%d\n",i);
            return 0;
        }

        sumx=sumx+x[i];
        sumy=sumy+y[i];

        ins(xx[i],x[i],0);
        ins(xx[i],1,1);
        ins(yy[i],y[i],2);
        ins(yy[i],1,3);
    }
    printf("-1");

    return 0;
}