Luogu1527 [国家集训队]矩阵乘法 (整体二分)（Unfinished）

全线RE的代码。。。先搁这吧，下次再说.flag
//#include <iostream>

#include <cstdio>

//#include <cstring>

#include <algorithm>

//#include <cmath>

#define R(a,b,c) for(register int  a = (b); a <= (c); ++ a)

#define nR(a,b,c) for(register int  a = (b); a >= (c); -- a)

#define Max(a,b) ((a) > (b) ? (a) : (b))

#define Min(a,b) ((a) < (b) ? (a) : (b))

#define Fill(a,b) memset(a, b, sizeof(a))

#define Swap(a,b) a^=b^=a^=b

#define ll long long

//#define ON_DEBUG

#ifdef ON_DEBUG

#define D_e_Line printf("\n\n----------\n\n")

#define D_e(x)  cout << #x << " = " << x << endl

#define Pause() system("pause")

#else

#define D_e_Line ;

#endif

struct ios{

    template<typename ATP>ios& operator >> (ATP &x){

        x = 0; int f = 1; char c;

        for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-')  f = -1;

        while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();

        x*= f;

        return *this;

    }

}io;

using namespace std;

const int N = 507;

const int M = 60007;

int n;

struct Matrix{

    int x, y, val;

    bool operator < (const Matrix &com) const{

		return val < com.val;

	}

}mp[N*N];

int cnt;

struct Questions{

    int xx1, yy1, xx2, yy2, K;

}q[M];

int t[N][N];

inline void Updata(int x, int y, int val){

    for(register int i = x; i <= n; i += i&-i)

        for(register int j = y; j <= n; j += j&-j)

			t[i][j] += val;

}

inline int Query(int x, int y){

    int s = 0;

    for(register int i = x; i; i -= i&-i)

        for(register int j = y; j; j -= j&-j)

			s += t[i][j];

    return s;

}

// I don't know what happend below

//inline void Updata(int x, int y, int val){

//    for(; x <= n; x += x&-x)

//        for(; y <= n; y += y&-y)

//			t[x][y] += val;

//}

//inline int Query(int x, int y){

//    int s = 0;

//    for(; x; x -= x&-x)

//        for(; y; y -= y&-y)

//			s += t[x][y];

//    return s;

//}

inline int Calc(int xx1, int yy1, int xx2, int yy2){

    return Query(xx2, yy2)-Query(xx2, yy1-1)-Query(xx1-1, yy2)+Query(xx1-1, yy1-1);

}

int id[N],siz[N],ans[N];

int tmp[N], tmp1[N], tmp2[N];

inline void Dictomy(int l, int r, int L, int R){

    if(L > R) return;

    if(l == r){

        R(i,L,R)

			ans[id[i]] = mp[l].val;

        return;

    }

    int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0;

    R(i,l,mid) Updata(mp[i].x, mp[i].y, 1);

    R(i,L,R){

        int sum = Calc(q[id[i]].xx1, q[id[i]].yy1, q[id[i]].xx2, q[id[i]].yy2);

        if(siz[id[i]]+sum >= q[id[i]].K){

        	tmp1[++cnt1] = id[i];

        }

        else{

         	siz[id[i]] += sum;

			tmp2[++cnt2] = id[i];

        }

    }

    R(i,l,mid) Updata(mp[i].x, mp[i].y, -1);

    int qCnt = L-1;

    R(i,1,cnt1){

    	tmp[++qCnt] = tmp1[i];

		id[qCnt] = tmp[qCnt];

    }

    R(i,1,cnt2){

    	tmp[++qCnt] = tmp2[i];

		id[qCnt] = tmp[qCnt];

    }

    Dictomy(l, mid, L, L + cnt1 - 1);

    Dictomy(mid + 1, r, L + cnt1, R);

}

//#define FileInTheHole

int main(){

//#ifdef FileInTheHole

//	D_e_Line;

//    freopen("in.txt", "r", stdin);

//#endif

	int Que;

	io >> n >> Que;

    R(i,1,n){

    	R(j,1,n){

    		int x;

    		io >> x;

    		mp[++cnt] = (Matrix){i, j, x};

    	}

    }

    sort(mp + 1, mp + cnt + 1);

    R(i,1,Que){

    	io >> q[i].xx1 >> q[i].yy1 >> q[i].xx2 >> q[i].yy2 >> q[i].K;

		id[i] = i;

    }

    Dictomy(1, cnt, 1, Que);

    R(i,1,Que)

		printf("%d\n", ans[i]);

    return 0;

}
参考博客
巴特西

Luogu1527 [国家集训队]矩阵乘法 (整体二分)（Unfinished）

最新文章

热门文章
