K大数查询 BZOJ 3110

K大数查询

【问题描述】

有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。

【输入格式】

第一行N，M

接下来M行，每行形如1 a b c或2 a b c

【输出格式】

输出每个询问的结果

【样例输入】

2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3

【样例输出】

1
2
1

【样例说明】

第一个操作后位置 1 的数只有 1 ，位置 2 的数也只有 1 。

第二个操作后位置 1的数有 1 、 2 ，位置 2 的数也有 1 、 2 。

第三次询问位置 1 到位置 1 第 2 大的数是1 。

第四次询问位置 1 到位置 1 第 1 大的数是 2 。

第五次询问位置 1 到位置 2 第 3大的数是 1 。‍

【数据范围】

N,M<=50000，N,M<=50000，a<=b<=N

1操作中abs(c)<=N，2操作中c<=Maxlongint

题解：

我们将询问离线，做整体二分

题目中有负数，那么我们转化一下，将每个数变为n-i+1，输出答案时再变为n-ans+1

对于一个操作1，如果这个操作加入的c是不超过mid的

用线段树在区间内加1，表示此区间小于等于mid的数多了一个，那么将它放置到左区间

否则将其放置到右区间，表示这个操作的贡献在右区间

对于一个操作2，查询在区间内小于等于mid的数的个数tot

如果tot超过k，将其放置到左区间，表示答案在左区间

否则将k减去tot，放置到右区间，表示需要在右区间找k-tot大的数

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 struct S { long long x, y, z, id, flag; } a[], c[];

 bool lr[];

 long long n, m, tot, maxx = -;

 long long sum[], ans[], node[];

 void Down(long long k, int l, int r)

 {

     if(node[k] != )

     {

         int mi = (l + r) >> ;

         node[k * ] += node[k];

         node[k *  + ] += node[k];

         sum[k * ] += node[k] * (mi - l + );

         sum[k *  + ] += node[k] * (r - mi);

         node[k] = ;

     }

 }

 void Inc(int k, int l, int r, int x, int y, int z)

 {

     if(x <= l && r <= y)

     {

         sum[k] += z * (r - l + );

         node[k] += z;

         return;

     }

     Down(k, l, r);

     int mi = (l + r) >> ;

     if(mi >= x) Inc(k * , l, mi, x, y, z);

     if(mi < y) Inc(k *  + , mi + , r, x, y, z);

     sum[k] = sum[k * ] + sum[k *  + ];

 }

 long long Sum(long long k, long long l, long long r, long long x, long long y)

 {

     if(x <= l && r <= y) return sum[k];

     Down(k, l, r);

     long long mi = (l + r) >> , res = ;

     if(mi >= x) res += Sum(k * , l, mi, x, y);

     if(mi < y) res += Sum(k *  + , mi + , r, x, y);

     return res;

 }

 void Two(long long x, long long y, long long l, long long r)

 {

     cout<<x<<' '<<y<<' '<<l<<' '<<r<<endl;

     long long mi = (l + r) >> ;

     if(l == r)

     {

         for(int i = x; i <= y; ++i)

             if(a[i].flag)

                 ans[a[i].id] = mi;

         return;

     }

     long long temp, s = x;

     for(int i = x; i <= y; ++i)

     {

         if(a[i].flag)

         {

             temp = Sum(, ,  * n + , a[i].x, a[i].y);

             if(temp < a[i].z)

             {

                 a[i].z -= temp;

                 lr[i] = false;

             }

             else

             {

                 ++s;

                 lr[i] = true;

             }

         }

         else

         {

             if(a[i].z <= mi)

             {

                 Inc(, ,  * n + , a[i].x, a[i].y, );

                 ++s;

                 lr[i] = true;

             }

             else lr[i] = false;

         }

     }

     for(int i = x; i <= y; ++i)

         if(!a[i].flag && a[i].z <= mi)

             Inc(, ,  * n + , a[i].x, a[i].y, -);

     long long o = x;

     for(int i = x; i <= y; ++i)

         if(lr[i]) c[o++] = a[i];

         else c[s++] = a[i];

     for(int i = x; i <= y; ++i) a[i] = c[i];

     Two(x, o - , l, mi), Two(o, y, mi + , r);

 }

 int main()

 {

     scanf("%lld%lld", &n, &m);

     for(int i = ; i <= m; ++i)

     {

         scanf("%lld%lld%lld%lld", &a[i].flag, &a[i].x, &a[i].y, &a[i].z);

         --a[i].flag;

         if(!a[i].flag)

         {

             a[i].z = n - a[i].z + ;

             maxx = (a[i].z > maxx) ? a[i].z : maxx;

         }

         else a[i].id = ++tot;

     }

     Two(, m, , maxx);

     for(int i = ; i <= tot; ++i) printf("%lld\n", n - ans[i] + );

 }

巴特西

K大数查询 BZOJ 3110

最新文章

热门文章