suyiheng @ 2019-07-10 10:20:58
RT,整体二分+二维线段树
#include<iostream>
#include<cstdio>
using namespace std;
struct data{
int x,y,x1,y1,k,s,id;
}f[400001],k1[400001],k2[400001];
int n,m,ans[60001],cnt,x=1000000000,y=0,t[1000001];
void ins(int s,int l1,int r1,int l2,int r2,int ql,int qr){
if(l1>ql||l2<ql||r1>qr||r2<qr)return;
if(l1==l2&&r1==r2){
t[s]++;
return;
}
int mid1=(l1+l2)/2,mid2=(r1+r2)/2;
if(l1==l2){
ins(s*4-2,l1,r1,l2,mid2,ql,qr);
ins(s*4-1,l1,mid2+1,l2,r2,ql,qr);
t[s]=t[s*4-2]+t[s*4-1];
return;
}else if(r1==r2){
ins(s*4-2,l1,r1,mid1,r2,ql,qr);
ins(s*4-1,mid1+1,r1,l2,r2,ql,qr);
t[s]=t[s*4-2]+t[s*4-1];
return;
}
ins(s*4-2,l1,r1,mid1,mid2,ql,qr);
ins(s*4-1,l1,mid2+1,mid1,r2,ql,qr);
ins(s*4,mid1+1,r1,l2,mid2,ql,qr);
ins(s*4+1,mid1+1,mid2+1,l2,r2,ql,qr);
t[s]=t[s*4-2]+t[s*4-1]+t[s*4]+t[s*4+1];
return;
}
int get_ans(int s,int l1,int r1,int l2,int r2,int ql1,int qr1,int ql2,int qr2){
if(l1>ql2||l2<ql1||r1>qr2||r2<qr1)return 0;
if(ql1<=l1&&l2<=ql2&&qr1<=r1&&r2<=qr2)return t[s];
int mid1=(l1+l2)/2,mid2=(r1+r2)/2;
if(l1==l2){
int p1=get_ans(s*4-2,l1,r1,l2,mid2,ql1,qr1,ql2,qr2),p2=get_ans(s*4-1,l1,mid2+1,l2,r2,ql1,qr1,ql2,qr2);
return p1+p2;
}else if(r1==r2){
int p1=get_ans(s*4-2,l1,r1,mid1,r2,ql1,qr1,ql2,qr2),p2=get_ans(s*4-1,mid1+1,r1,l2,r2,ql1,qr1,ql2,qr2);
return p1+p2;
}
int p1=get_ans(s*4-2,l1,r1,mid1,mid2,ql1,qr1,ql2,qr2),p2=get_ans(s*4-1,l1,mid2+1,mid1,r2,ql1,qr1,ql2,qr2),p3=get_ans(s*4,mid1+1,r1,l2,mid2,ql1,qr1,ql2,qr2),p4=get_ans(s*4+1,mid1+1,mid2+1,l2,r2,ql1,qr1,ql2,qr2);
return p1+p2+p3+p4;
}
void clean(int s,int l1,int r1,int l2,int r2){
if(t[s]==0)return;
t[s]=0;
if(l1==l2&&r1==r2)return;
int mid1=(l1+l2)/2,mid2=(r1+r2)/2;
if(l1==l2){
clean(s*4-2,l1,r1,l2,mid2);
clean(s*4-1,l1,mid2+1,l2,r2);
return;
}else if(r1==r2){
clean(s*4-2,l1,r1,mid1,r2);
clean(s*4-1,mid1+1,r1,l2,r2);
return;
}
clean(s*4-2,l1,r1,mid1,mid2);
clean(s*4-1,l1,mid2+1,mid1,r2);
clean(s*4,mid1+1,r1,l2,mid2);
clean(s*4+1,mid1+1,mid2+1,l2,r2);
}
void find(int l,int r,int ql,int qr){
if(ql>qr)return;
if(l==r){
for(int i=ql;i<=qr;i++)if(f[i].id)ans[f[i].s]=l;
return;
}
int mid=(l+r)/2,cnt1=0,cnt2=0;
for(int i=ql;i<=qr;i++){
if(f[i].id){
int a=get_ans(1,1,1,n,n,f[i].x,f[i].y,f[i].x1,f[i].y1);
if(a>=f[i].k){
cnt1++;
k1[cnt1]=f[i];
}else{
cnt2++;
k2[cnt2]=f[i];
k2[cnt2].k=k2[cnt2].k-a;
}
}else{
if(f[i].k<=mid){
cnt1++;
k1[cnt1]=f[i];
ins(1,1,1,n,n,f[i].x,f[i].y);
}else{
cnt2++;
k2[cnt2]=f[i];
}
}
}
clean(1,1,1,n,n);
for(int i=1;i<=cnt1;i++)f[ql+i-1]=k1[i];
for(int i=1;i<=cnt2;i++)f[ql+i+cnt1-1]=k2[i];
find(l,mid,ql,ql+cnt1-1);
find(mid+1,r,ql+cnt1,qr);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cnt++;
f[cnt].x=i;
f[cnt].y=j;
scanf("%d",&f[cnt].k);
x=min(x,f[cnt].k);
y=max(y,f[cnt].k);
f[cnt].s=1;
f[cnt].id=0;
}
}
for(int i=1;i<=m;i++){
cnt++;
scanf("%d%d%d%d%d",&f[cnt].x,&f[cnt].y,&f[cnt].x1,&f[cnt].y1,&f[cnt].k);
f[cnt].s=i;
f[cnt].id=1;
}
find(x,y,1,cnt);
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}by suyiheng @ 2019-07-10 10:21:22
20分，TLE
by ez_lcw @ 2019-07-10 10:21:31
orz SYH神仙！！！
by ez_lcw @ 2019-07-10 10:21:41
tql
by RiverFun @ 2019-07-10 10:27:14
@suyiheng 把二维线段树换成二维树状数组
by 逃课小姐MS @ 2019-07-10 10:42:41
@suyiheng 头像白面鸽好评
by suyiheng @ 2019-07-10 10:46:28
@RiverFun 还是TLE,时间貌似比线段树做的还要大
#include<iostream>
#include<cstdio>
using namespace std;
struct data{
int x,y,x1,y1,k,s,id;
}f[400001],k1[400001],k2[400001];
int n,m,ans[60001],cnt,x=1000000000,y=0,t[501][501];
int get(int a){
return a&(-a);
}
void ins(int a,int b){
for(int i=a;i<=n;i+=get(i))for(int j=b;j<=n;j+=get(j))t[i][j]++;
}
int pre(int x,int y) {
int ans=0;
for(int i=x;i>0;i-=get(i))for(int j=y;j>0;j-=get(j))ans+=t[i][j];
return ans;
}
int get_ans(int x1,int y1,int x2,int y2){
int w=pre(x2,y2);
w-=pre(x1-1,y2)+pre(x2,y1-1);
w+=pre(x1-1,y1-1);
return w;
}
void clean(){
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)t[i][j]=0;
}
void find(int l,int r,int ql,int qr){
if(ql>qr)return;
if(l==r){
for(int i=ql;i<=qr;i++)if(f[i].id)ans[f[i].s]=l;
return;
}
int mid=(l+r)/2,cnt1=0,cnt2=0;
for(int i=ql;i<=qr;i++){
if(f[i].id){
int a=get_ans(f[i].x,f[i].y,f[i].x1,f[i].y1);
if(a>=f[i].k){
cnt1++;
k1[cnt1]=f[i];
}else{
cnt2++;
k2[cnt2]=f[i];
k2[cnt2].k=k2[cnt2].k-a;
}
}else{
if(f[i].k<=mid){
cnt1++;
k1[cnt1]=f[i];
ins(f[i].x,f[i].y);
}else{
cnt2++;
k2[cnt2]=f[i];
}
}
}
clean();
for(int i=1;i<=cnt1;i++)f[ql+i-1]=k1[i];
for(int i=1;i<=cnt2;i++)f[ql+i+cnt1-1]=k2[i];
find(l,mid,ql,ql+cnt1-1);
find(mid+1,r,ql+cnt1,qr);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cnt++;
f[cnt].x=i;
f[cnt].y=j;
scanf("%d",&f[cnt].k);
x=min(x,f[cnt].k);
y=max(y,f[cnt].k);
f[cnt].s=1;
f[cnt].id=0;
}
}
for(int i=1;i<=m;i++){
cnt++;
scanf("%d%d%d%d%d",&f[cnt].x,&f[cnt].y,&f[cnt].x1,&f[cnt].y1,&f[cnt].k);
f[cnt].s=i;
f[cnt].id=1;
}
find(x,y,1,cnt);
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}by 樱花树下少年 @ 2019-07-10 10:56:42
@suyihcng用这个``` // luogu-judger-enable-o2
using namespace std;
inline int geti() { int ans = 0; bool flag = 0; char c = getchar(); while(!isdigit(c)) flag |= c == '-', c = getchar(); while( isdigit(c)) ans=ans*10+c-'0', c = getchar(); return flag? -ans: ans; }
inline void puti(int x) { if(x < 0) x=-x, putchar('-'); if(x > 9) puti(x / 10); putchar('0' + x%10); }
const int maxn = 500 + 10, maxq = 60000 + 5;
struct Numbers { int x, y, v; /// (x,y) 位置的值为 v bool operator < (const Numbers& rhs) const { return v < rhs.v; /// 用于比较大小 } } Matrix[maxn * maxn]; int mcnt; /// 矩阵中的元素个数
struct BIT { int n; /// n * n 的二维树状数组 int C[maxn][maxn]; BIT(int N = 0) {n = N; memset(C, 0x00, sizeof(C));} /// 初始化 inline int lowbit(int x) {return x&(-x);} inline void add(int x, int y, int v) { /// 单点修改 for(register int i = x; i <= n; i += lowbit(i)) for(register int j = y; j <= n; j += lowbit(j)) C[i][j] += v; } inline int pre(int x, int y) { /// 前缀求和 int ans = 0; for(register int i = x; i > 0; i -= lowbit(i)) for(register int j = y; j > 0; j -= lowbit(j)) ans += C[i][j]; return ans; } inline int submat(int x1, int y1, int x2, int y2) { /// 子矩阵和 int ans = pre(x2, y2); ans -= pre(x1 - 1, y2) + pre(x2, y1 - 1); ans += pre(x1 - 1, y1 - 1); return ans; } } bit; /// 记得初始化 n
struct Events { /// 记录所有询问 int x1, y1, x2, y2, k; inline void input() { /// 输入一个询问 x1 = geti(); y1 = geti(); x2 = geti(); y2 = geti(); k = geti(); } } Querys[maxq];
int bcount(Events mat) { /// 查询某个询问中的黑点个数 return bit.submat(mat.x1, mat.y1, mat.x2, mat.y2); }
int id[maxq], t1[maxq], t2[maxq]; int ans[maxq], cur[maxq];
void Sol(int l, int r, int ql, int qr) { if(qr < ql) return; /// 该值域区间没有询问 if(l == r) { for(int i = ql; i <= qr; i ++) ans[id[i]] = Matrix[l].v; return; /// 找到解 } int mid = (l + r)/2; for(int i = l; i <= mid; i ++) /// 把要统计到答案中的数值染黑 bit.add(Matrix[i].x, Matrix[i].y, 1); int cnt1 = 0, cnt2 = 0; for(int i = ql; i <= qr; i ++) { int u = id[i]; /// 当前要处理的询问 int s = cur[u] + bcount(Querys[u]); /// 考虑当前区间中的黑点个数 if(s >= Querys[u].k) t1[++ cnt1] = u; else t2[++ cnt2] = u, cur[u] = s; } int qcnt = ql - 1; for(int i = 1; i <= cnt1; i ++) id[++ qcnt] = t1[i]; /// 左右分组 for(int i = 1; i <= cnt2; i ++) id[++ qcnt] = t2[i]; for(int i = l; i <= mid; i ++) /// 谁污染谁治理 bit.add(Matrix[i].x, Matrix[i].y, -1); Sol(l, mid, ql, ql + cnt1 - 1); Sol(mid+1, r, ql + cnt1, qr); }
int main() { int N = geti(), Q = geti(); bit.n = N;/// 输入矩阵大小和询问组数 for(int i = 1; i <= N; i ++) for(int j = 1; j <= N; j ++) Matrix[++ mcnt] = (Numbers){i, j, geti()}; sort(Matrix + 1, Matrix + mcnt + 1); /// 按元素大小从小到大排序 for(int i = 1; i <= Q; i ++) Querys[i].input(); for(int i = 1; i <= Q; i ++) id[i] = i; Sol(1, mcnt, 1, Q); for(int i = 1; i <= Q; i ++) puti(ans[i]), putchar('\n'); return 0; }
by suyiheng @ 2019-07-10 11:22:31
@樱花树下少年 希望更丰富的展现？使用Markdown