C106 整体二分+树状数组 P1527 [国家集训队] 矩阵乘法

// 整体二分+树状数组 O(q*logn*logn*logV)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define lowbit(x) (x&-x)
const int N=60005;
int n,m,ans[N];
struct Q{
  //查询: (x,y)(u,v)的第k小，id编号，opt=1
  //原数: (x,y)位置，k值，opt=0
  int x,y,u,v,k,id,opt;
};
vector<Q>q; //数据序列

struct BIT{
  vector<vector<int> >s;
  void init(int n){ //初始化s
    s.resize(n);
    for(int i=1;i<=n;i++)s[i].resize(n);
  }
  void add(int x,int y,int v){ //加入贡献

C106 整体二分+树状数组 P1527 [国家集训队] 矩阵乘法

// 整体二分+树状数组 O(qlognlogn*logV)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define lowbit(x) (x&-x) const int N=60005; int n,m,ans[N]; struct Q{ //查询: (x,y)(u,v)的第k小，id编号，opt=1 //原数: (x,y)位置，k值，opt=0 int x,y,u,v,k,id,opt; }; vector<Q>q; //数据序列

struct BIT{ vector<vector<int> >s; void init(int n){ //初始化s s.resize(n); for(int i=1;i<=n;i++)s[i].resize(n); } void add(int x,int y,int v){ //加入贡献 for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=n;j+=lowbit(j)) s[i][j]+=v; } int sum(int x,int y){ int t=0; for(int i=x;i;i-=lowbit(i)) for(int j=y;j;j-=lowbit(j)) t+=s[i][j]; return t; } int sum(int x,int y,int u,int v){//区间和 return sum(u,v)-sum(x-1,v) -sum(u,y-1)+sum(x-1,y-1); } }tree; //树状数组

void solve(vector<Q>q,int L,int R){ if(!q.size()) return; if(L==R){ for(auto i:q) if(i.opt) ans[i.id]=L; return; } int mid=L+R>>1; vector<Q>q1,q2; for(auto i:q){ if(!i.opt){ //若是原数，按值分流 if(i.k<=mid) tree.add(i.x,i.y,1), //加入贡献 q1.push_back(i); //分流到左边 else q2.push_back(i); //分流到右边 } else{ //若是查询，按个数分流 int s=tree.sum(i.x,i.y,i.u,i.v); if(s>=i.k) q1.push_back(i); //分流到左边 else i.k-=s,q2.push_back(i);//分流到右边 } } for(auto i:q1) if(!i.opt)tree.add(i.x,i.y,-1); //减去贡献 solve(q1,L,mid); solve(q2,mid+1,R); //分治 } int main(){ scanf("%d%d",&n,&m); int x,y,u,v,k; tree.init(n+1); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&x),q.push_back({i,j,0,0,x,0,0}); for(int i=1;i<=m;i++) scanf("%d%d%d%d%d",&x,&y,&u,&v,&k), q.push_back({x,y,u,v,k,i,1}); solve(q,0,1e9); //整体二分 for(int i=1;i<=m;i++)printf("%d\n",ans[i]); }</pre>