青岛网站设计模板,建材在哪些网站做,手机net网站开发,wordpress主题如何开发题目
洛谷题目链接
题解
题目的数据范围非常奇怪#xff0c;一半是200∗200200∗200的矩阵#xff0c;另一半是1∗500001∗50000的矩阵#xff0c;显然是一道二合一的题目#xff0c;但是不一样的地方也就在与数据结构的选择不一样#xff0c;而我们解这道题使用的算法…题目
洛谷题目链接
题解
题目的数据范围非常奇怪一半是200∗200200∗200200*200的矩阵另一半是1∗500001∗500001*50000的矩阵显然是一道二合一的题目但是不一样的地方也就在与数据结构的选择不一样而我们解这道题使用的算法是一样的即都是二分法。
这道题所需要的数据结构应该能提供如下的功能在O(1)O(1)O(1)或O(logn)O(logn)O(logn)的时间复杂度内查询矩阵某区间内厚度大于xxx的书本数，以及厚度大于x" role="presentation" style="position: relative;">xxx的书的页数总和。
根据上述数据结构的功能我们可以设计一个二分算法。
即我们二分我们选取的书的最小厚度midmidmid。checkcheckcheck时候就checkcheckcheck一下矩阵内厚度≥mid≥mid≥mid的所有书的厚度之和是否能达到要求。 这样的话二分完之后所有厚度大于lll的书的个数就是我们的答案！
错！因为有可能厚度等于l" role="presentation" style="position: relative;">lll的书被多余使用了因此我们还要去掉一部分厚度为lll的书，使得总厚度仍然满足要求，但是答案变小。算法我们已经涉及完了。
现在我们想一下怎么样设计数据结构：
当矩阵大小为200#x2217;200" role="presentation" style="position: relative;">200∗200200∗200200*200的时候我们定义val[i][j][k]val[i][j][k]val[i][j][k]表示矩阵区间[1,i][1,j][1,i][1,j][1,i][1,j]部分厚度≥k≥k≥k的书的总厚度类似的定意num[i][j][k]num[i][j][k]num[i][j][k]表示个数。 这样只需要dpdpdp一下就ok了。
当矩阵大小为1∗5000001∗5000001*500000的时候涉及到区间操作我们可以使用两棵主席树一颗维护和另一颗维护个数。
代码
// luogu-judger-enable-o2
#include iostream
#include cstdio
#include cstring
#include algorithm
#define pr(x) cout#x:xendl
using namespace std;
const int maxn 500007;
struct segtree{int root[maxn*20];int val[maxn*20];int lson[maxn*20];int rson[maxn*20];int id 0;void init(){memset(root,0,sizeof(root));memset(val,0,sizeof(val));memset(lson,0,sizeof(lson));memset(rson,0,sizeof(rson));id 0;}int ins(int rt,int l,int r,int pos,int v){int nrt id;lson[nrt] lson[rt];rson[nrt] rson[rt];val[nrt] val[rt] v;rt nrt;if(l r) return 0;int mid (lr)/2;if(pos mid) ins(lson[rt],l,mid,pos,v);else ins(rson[rt],mid1,r,pos,v);}int query(int rt,int l,int r,int ul,int ur){if(!rt || ul r || ur l) return 0;if(ul l r ur) return val[rt];int mid (lr)/2;int r1 query(lson[rt],l,mid,ul,ur);int r2 query(rson[rt],mid1,r,ul,ur);return r1r2;}
}*seg,*segcnt;
int R,C,M;
int ck1(int mid,int y1,int y2){int sm seg-query(seg-root[y2],1,1000,mid,1000);sm - seg-query(seg-root[y1-1],1,1000,mid,1000);return sm;
}
void solve1(){seg new segtree;segcnt new segtree;seg-init();segcnt-init();for(int i 1;i C;i){int v;scanf(%d,v);seg-root[i] seg-root[i-1];segcnt-root[i] segcnt-root[i-1];seg-ins(seg-root[i],1,1000,v,v);segcnt-ins(segcnt-root[i],1,1000,v,1);}for(int i 1;i M;i){int x1,y1,x2,y2,h;scanf(%d%d%d%d%d,x1,y1,x2,y2,h);int l 1,r 1000;while(l r){int mid (lr1) / 2;if(ck1(mid,y1,y2) h) l mid;else r mid-1;}if(ck1(l,y1,y2) h) puts(Poor QLW);else {int ans segcnt-query(segcnt-root[y2],1,1000,l,1000);ans - segcnt-query(segcnt-root[y1-1],1,1000,l,1000);int delta ck1(l,y1,y2) - h;ans - delta / l;printf(%d\n,ans);}}
}
int (*val)[201][1001],(*vc)[201][1001];
int ck2(int va[201][201][1001],int mid,int x1,int y1,int x2,int y2){int ans va[x2][y2][mid] va[x1-1][y1-1][mid]- va[x2][y1-1][mid] - va[x1-1][y2][mid];return ans;
}
void solve2(){val new int[201][201][1001];vc new int[201][201][1001];memset(val,0,sizeof(val));memset(vc,0,sizeof(vc));for(int i 1;i R;i) for(int j 1;j C;j){int tmp;scanf(%d,tmp);for(int k 1;k 1000;k){val[i][j][k] val[i][j-1][k] val[i-1][j][k]- val[i-1][j-1][k];vc[i][j][k] vc[i][j-1][k] vc[i-1][j][k] - vc[i-1][j-1][k];if(tmp k) val[i][j][k] tmp,vc[i][j][k] ; }}for(int i 1;i M;i){int x1,y1,x2,y2,h;scanf(%d%d%d%d%d,x1,y1,x2,y2,h);int l 1,r 1000;while(l r){int mid (lr1) / 2;if(ck2(val,mid,x1,y1,x2,y2) h) l mid;else r mid-1;}if(ck2(val,l,x1,y1,x2,y2) h) puts(Poor QLW);else {int ans ck2(vc,l,x1,y1,x2,y2);int delta (ck2(val,l,x1,y1,x2,y2)-h)/l;ans - delta;printf(%d\n,ans);}}
}int main()
{cinRCM;if(R 1) solve1();else solve2();return 0;
}
