Hacker Cups and Balls Gym - 101234A 二分+线段树

题意:有编号从1到n的n个球和n个杯子. 每一个杯子里有一个球, 进行m次排序操作，每次操作给出l,r. 如果l<r，将[l,r]范围内的球按升序排序, 否则降序排, 问中间位置的数是多少.

思路:

　　暴力复杂度为m*nlog(n), 不能暴力排序

　　二分答案, 对于当前mid, 我们将大于等于mid的数记为1, 否则记0, 则排序就是将某个区间的数改为1或0, 通过线段树区间更新可以方便的做到, 对排序后的结果查询判断二分区间应该取左还是取右, 若中间的数是1, 则说明答案大于等于当前的数, l右移, 否则左移

AC代码:

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 #include <string>

 #include <map>

 #include <set>

 #include <unordered_map>

 #include <unordered_set>

 #include <queue>

 #include <stack>

 #include <list>

 #define FRER() freopen("in.txt", "r", stdin)

 #define FREW() freopen("out.txt", "w", stdout)

 #define INF 0x3f3f3f3f

 #define eps 1e-8

 using namespace std;

 const int maxn = 1e5 + ;

 int a[maxn], ql[maxn], qr[maxn], tree[maxn << ], lazy[maxn << ];

 void build(int l, int r, int rt, int num) {

     lazy[rt] = ;

     if(l == r) {

         tree[rt] = (a[l] >= num);

         return ;

     }

     int m = (l + r) >> ;

     build(l, m, rt << , num);

     build(m + , r, rt << |, num);

     tree[rt] = tree[rt << ] + tree[rt << |];

 }

 void pushdown(int l, int r, int rt) {

     int m = (l + r) >> ;

     lazy[rt << ] = lazy[rt << |] = lazy[rt];

     if(lazy[rt] == ) {

         tree[rt << |] = min(tree[rt], r - m);

         tree[rt << ] = tree[rt] - tree[rt << |];

     }

     else if(lazy[rt] == ){

         tree[rt << ] = min(tree[rt], m - l + );

         tree[rt << |] = tree[rt] - tree[rt << ];

     }

     lazy[rt] = ;

 }

 int querySum(int x, int y, int l, int r, int rt) {

     if(x <= l && y >= r) return tree[rt];

     if(lazy[rt]) pushdown(l, r, rt);

     int m = (l + r) >> , sum = ;

     if(x <= m) sum += querySum(x, y, l, m, rt << );

     if(y > m) sum += querySum(x, y, m + , r, rt << |);

     return sum;

 }

 int query(int pos, int l, int r, int rt) {

     if(l == r) return tree[rt];

     if(lazy[rt]) pushdown(l, r, rt);

     int m = (l + r) >> ;

     if(pos <= m) return query(pos, l, m, rt << );

     else return query(pos, m + , r, rt << |);

 }

 void update(int x, int y, int l, int r, int rt, int flag, int sum) {

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

         tree[rt] = sum;

         lazy[rt] = flag;

         return ;

     }

     if(lazy[rt]) pushdown(l, r, rt);

     int m = (l + r) >> ;

     if(y <= m) update(x, y, l, m, rt << , flag, sum);

     else if(x > m) update(x, y, m + , r, rt << |, flag, sum);

     else {

         int lsum, rsum;

         if(flag== ) {

             rsum = min(sum, y - m);

             lsum = sum - rsum;

         }

         else if(flag == ){

             lsum = min(sum, m - x + );

             rsum = sum - lsum;

         }

         update(x, m, l, m, rt << , flag, lsum);

         update(m + , y, m + , r, rt << |, flag, rsum);

     }

     tree[rt] = tree[rt << ] + tree[rt << |];

 }

 bool judge(int n, int m, int mid) {

     build(, n, , mid);

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

         int sum = querySum(min(ql[i], qr[i]), max(ql[i], qr[i]), , n, );

         if(ql[i] <= qr[i]) update(ql[i], qr[i], , n, , , sum);

         else update(qr[i], ql[i], , n, , , sum);

     }

     return query(( + n) >> , , n, );

 }

 int main()

 {

     //FRER();

     ios::sync_with_stdio();

     cin.tie();

     int n, m;

     cin >> n >> m;

     for(int i = ; i <= n; ++i) cin >> a[i];

     for(int i = ; i < m; ++i) cin >> ql[i] >> qr[i];

     int l = , r = n, ans;

     while(l <= r) {

         int mid = (l + r) >> ;

         if(judge(n, m, mid))

             ans = mid, l = mid + ;

         else r = mid - ;

     }

     cout << ans << endl;

     return ;

 }

巴特西

Hacker Cups and Balls Gym - 101234A 二分+线段树

最新文章

热门文章