专业制作彩铃网站,wordpress新建header,微信营销神器,做不规则几何图形的网站[SDOI2010]粟粟的书架
题意#xff1a;
一个R * C的矩阵#xff0c;每个位置都有个数page[ij]#xff0c;现在选定一个小矩阵范围(给左上角坐标#xff0c;和右下角坐标)#xff0c;问这个范围内的数总和是否大于h#xff0c;如果大于h的话最少选几个数aij 对于50%的数…[SDOI2010]粟粟的书架
题意
一个R * C的矩阵每个位置都有个数page[ij]现在选定一个小矩阵范围(给左上角坐标和右下角坐标)问这个范围内的数总和是否大于h如果大于h的话最少选几个数aij 对于50%的数据满足R, C≤200M≤200,000 另有50%的数据满足R1C≤500,000M≤20,000 对于100%的数据满足1≤Pi,j≤1,0001≤Hi≤2,000,000,000。
题解
题目数据给的很奇特一半是RC均小于200另一半R1(R1也就是只有一行) 对于前一半数据我们可以搞一个二位前缀和二分最小值 value[i][j][k]表示从(1,1)到(i,j)的矩阵中数值k的数的总和 num[i][j][k]表示从(1,1)到(i,j)的矩阵中数值k的个数 value是为了计算区间总和是否大于hnum用于二分选择数的最小值 num和val的维护就是前缀和经典的容斥原理
if(page[i][j]k)value[i][j][k]value[i-1][j][k]value[i][j-1][k]-value[i-1][j-1][k]page[i][j];
else value[i][j][k]value[i-1][j][k]value[i][j-1][k]-value[i-1][j-1][k]0;if(page[i][j]k)num[i][j][k]num[i-1][j][k]num[i][j-1][k]-num[i-1][j-1][k]1;
else num[i][j][k]num[i-1][j][k]num[i][j-1][k]-num[i-1][j-1][k]0;对于后一半数据R1C5∗1055*10^55∗105,就不能用二位前缀和了依旧是二分最小值直接主席树就可以
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
using namespace std;
typedef long long ll;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll1e18;
const int INF_int0x3f3f3f3f;
inline ll read(){ll s0,w1ll;char chgetchar();while(ch0||ch9){if(ch-)w-1ll;chgetchar();}while(ch0ch9) ss*10ll((ch-0)*1ll),chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
void rd_test(){#ifdef ONLINE_JUDGE#elsestartTime clock(); //计时开始freopen(in.txt,r,stdin);#endif
}
void Time_test(){#ifdef ONLINE_JUDGE#elseendTime clock(); //计时结束printf(\n运行时间为:%lfs\n,(double)(endTime - startTime) / CLOCKS_PER_SEC);#endif
}
int r,c,m;
const int maxn204;
ll val[maxn][maxn][1003];
int page[maxn][maxn];
int num[maxn][maxn][1004];
inline ll getval(int a,int b,int x,int y,int k){return val[x][y][k]-val[x][b-1][k]-val[a-1][y][k]val[a-1][b-1][k];
}
inline ll getnum(int a,int b,int x,int y,int k){return num[x][y][k]-num[x][b-1][k]-num[a-1][y][k]num[a-1][b-1][k];
}
void work2(){int maxx0;for(int i1;ir;i){for(int j1;jc;j){scanf(%d,page[i][j]);maxxmax(maxx,page[i][j]);}}for(int k0;kmaxx;k){for(int i1;ir;i){for(int j1;jc;j){if(page[i][j]k)val[i][j][k]val[i-1][j][k]val[i][j-1][k]-val[i-1][j-1][k]page[i][j];else val[i][j][k]val[i-1][j][k]val[i][j-1][k]-val[i-1][j-1][k]0;if(page[i][j]k)num[i][j][k]num[i-1][j][k]num[i][j-1][k]-num[i-1][j-1][k]1;else num[i][j][k]num[i-1][j][k]num[i][j-1][k]-num[i-1][j-1][k]0;}}}while(m--){int x1,y1,x2,y2;ll h;scanf(%d%d%d%d%lld,x1,y1,x2,y2,h);ll ansgetval(x1,y1,x2,y2,0);if(ansh)printf(Poor QLW\n);else {int l0,rmaxx1;while(l1r){int mid(lr)1;if(getval(x1,y1,x2,y2,mid)h)lmid;else rmid;}int maxnumgetnum(x1,y1,x2,y2,l);printf(%d\n,maxnum-((getval(x1,y1,x2,y2,l)-h)/l));}}
}
const int N5500002;
int L[N],R[N],size[N],sum[N],rt[N],cnt;
inline void update(int now,int pre,int l,int r,int x){nowcnt;size[now]size[pre]1;sum[now]sum[pre]x;L[now]L[pre];R[now]R[pre];if(lr)return ;int midlr1;if(xmid)update(L[now],L[pre],l,mid,x);else update(R[now],R[pre],mid1,r,x);
}
inline ll query(int Lrt,int Rrt,int l,int r,ll k){ll ans0;while(lr){int mid(lr)1;int Sumsum[R[Rrt]]-sum[R[Lrt]];//优先取较大值右侧 的数更大 if(Sumk){anssize[R[Rrt]]-size[R[Lrt]];k-Sum;rmid;RrtL[Rrt];LrtL[Lrt]; }else if(Sumk){lmid1;RrtR[Rrt];LrtR[Lrt]; }}//debug((kl-1)/l,(kl-1)/l);ans(kl-1)/l;return ans;
}
void work1(){int x;rt[0]0;for(int i1;ic;i){scanf(%d,x);update(rt[i],rt[i-1],1,1000,x);}while(m--){int x1,y1,x2,y2;ll h;scanf(%d%d%d%d%lld,x1,y1,x2,y2,h);if(sum[rt[y2]]-sum[rt[y1-1]]h){printf(Poor QLW\n);continue;}printf(%d\n,query(rt[y1-1],rt[y2],1,1000,h));}
}
int main()
{rd_test();cinrcm;if(r1)work1();else work2();//Time_test();return 0;
}
