BZOJ 2738: 矩陣乘法

2019-11-08 20:02:47

字體：大中小

來源：轉載

供稿：網友

整體二分

先把矩陣所有元素從小到大排序，然后對于每個矩形二分一個k，用二維樹狀數組check（即比他小的在那個矩形內的有多少個）。

復雜度好像是O(n?(logn)4) $O(n *(logn)^4)$

//QWsin#include<cmath>#include<vector>#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int maxn=500+10;const int maxn2=250000+10;const int maxq=60000+10;inline int read(){ int ret=0;char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); for(;ch>='0'&&ch<='9';ch=getchar()) ret=ret*10+ch-'0'; return ret;}int n,q,t[maxn2];int C[maxn][maxn];#define lowbit(i) ((i)&-(i))inline void updata(int x,int y,int val){ for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=n;j+=lowbit(j)) C[i][j]+=val; }inline int query(int x,int y){ int ret=0; for(int i=x;i;i-=lowbit(i)) for(int j=y;j;j-=lowbit(j)) ret+=C[i][j]; return ret; }inline int query(int a,int b,int c,int d){ return query(c,d)-query(c,b-1)-query(a-1,d)+query(a-1,b-1); }struct Node{ int x,y,num; inline bool Operator < (const Node &rhs)const{ return num<rhs.num; } inline void input(int i,int j){ x=i;y=j;num=read(); t[(i-1)*n+j]=num; }}a[maxn2];struct ASK{ int a,b,c,d,k,t,id; ASK(int a=0,int b=0,int c=0,int d=0,int k=0,int id=0): a(a),b(b),c(c),d(d),k(k),id(id){}};int top=0,ans[maxq];void solve(vector<ASK>ask,int l,int r){ if(l==r){ for(int i=0,sz=ask.size();i<sz;++i) ans[ask[i].id]=l; return ; } int mid=(l+r)>>1; while(top<mid){ ++top;updata(a[top].x,a[top].y,1); } while(top>mid){ updata(a[top].x,a[top].y,-1);--top; } vector<ASK>L,R; for(int i=0,sz=ask.size();i<sz;++i){ ASK p=ask[i]; int t=query(p.a , p.b , p.c , p.d); if(t>=p.k) L.push_back(ask[i]); else R.push_back(ask[i]); } solve(L,l,mid);solve(R,mid+1,r);}int main(){ freopen("std.in","r",stdin); cin>>n>>q; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) a[(i-1)*n+j].input(i,j); sort(a+1,a+n*n+1); sort(t+1,t+n*n+1); vector<ASK>ask; for(int i=1,a,b,c,d,k;i<=q;++i){ a=read();b=read();c=read();d=read();k=read(); ask.push_back(ASK(a,b,c,d,k,i)); }// for(int i=1;i<=n;++i) 臥槽啊你手殘到這種地步，莫名其妙多出來一個for，T上天，而且把cdq注釋了還是T上天。（手動再見） solve(ask,1,n*n);//[l,r]是排序后的數組里的值 for(int i=1;i<=q;++i)