Tsinsen A1333： 矩阵乘法（整体二分）

时间：2022-07-04 03:00:24

http://www.tsinsen.com/A1333

题意：……

思路：和之前的第k小几乎一样，只不过把一维BIT换成二维BIT而已。注意二维BIT写法QAQ

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <string>

 #include <cmath>

 #include <queue>

 #include <vector>

 #include <map>

 #include <set>

 #include <stack>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define N 350000

 typedef long long LL;

 struct P {

     int x1, x2, y1, y2, val, id;

     P () {}

     P (int x1, int y1, int x2, int y2, int val, int id) : x1(x1), y1(y1), x2(x2), y2(y2), val(val), id(id) {}

 } q[N], lq[N], rq[N];

 int bit[][], ans[N], n;

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

 void update(int x, int y, int w) {

     for(int i = x; i <= n; i += lowbit(i))

         for(int j = y; j <= n; j += lowbit(j)) bit[i][j] += w;

 }

 int query(int x, int y) {

     int ans = ;

     for(int i = x; i; i -= lowbit(i))

         for(int j = y; j; j -= lowbit(j)) ans += bit[i][j];

     return ans;

 }

 void Solve(int lask, int rask, int l, int r) {

     if(lask > rask || l > r) return ;

     if(l == r) {

         for(int i = lask; i <= rask; i++) if(q[i].id) ans[q[i].id] = l;

         return ;

     }

     int mid = (l + r) >> , lcnt = , rcnt = ;

     for(int i = lask; i <= rask; i++) {

         if(!q[i].id) {

             if(q[i].val <= mid) {

                 update(q[i].x1, q[i].y1, );

                 lq[++lcnt] = q[i];

             } else rq[++rcnt] = q[i];

         } else {

             int num = query(q[i].x2, q[i].y2) - query(q[i].x1 - , q[i].y2) - query(q[i].x2, q[i].y1 - ) + query(q[i].x1 - , q[i].y1 - );

             if(num >= q[i].val) lq[++lcnt] = q[i];

             else {

                 q[i].val -= num;

                 rq[++rcnt] = q[i];

             }

         }

     }

     for(int i = ; i <= lcnt; i++) if(!lq[i].id) update(lq[i].x1, lq[i].y1, -);

     for(int i = ; i <= lcnt; i++) q[lask+i-] = lq[i];

     for(int i = ; i <= rcnt; i++) q[lask+lcnt+i-] = rq[i];

     Solve(lask, lask + lcnt - , l, mid);

     Solve(lask + lcnt, rask, mid + , r);

 }

 int main() {

     int m, cnt = , a;

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

     memset(bit, , sizeof(bit));

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

         for(int j = ; j <= n; j++) {

             scanf("%d", &a); q[++cnt] = P(i, j, , , a, );

         }

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

         ++cnt; q[cnt].id = i;

         scanf("%d%d%d%d%d", &q[cnt].x1, &q[cnt].y1, &q[cnt].x2, &q[cnt].y2, &q[cnt].val);

     }

     Solve(, cnt, , INF);

     for(int i = ; i <= m; i++) printf("%d\n", ans[i]);

 }

相关文章