[Sdoi2010 粟粟的书架]线段树、归并排序思想、桶

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1926
【算法分析】
前半部分，直接开200*200个1000的桶，利用经典的O(1)取子矩阵和的那种思想。复杂度做到了
O(Q*1000+R*C*1000)。
后半部分，弄一个线段树然后利用归并的思想把它映射到线性表上，然后二分答案再利用线段树二分线性表上的位置，最终得出ans。
时间复杂度O(Q*lg 1000 * lg c * lg c)。

【其它】
Orz。一开始第一部分用二维线段树做，直接TLE到SB。
线性表的话复杂度达到O(Q * lg 1000 * lg r * lg c * lg r*c)。
桶的话复杂度达到O(Q * lg 1000* lg r * lg c)。但是空间受不了。。。
跑得全世界最慢。
1 23199 root 157204K 4435MS Pascal 3.82K 2010-05-14 14:07:37 2 23435 oimaster 100112K 5574MS G++ 4.15K 2010-05-15 22:54:09 3 24878 edward_mj 164928K 9324MS G++ 4.45K 2010-05-21 20:25:45 【CODE】
#include #include #include const int N=205;
const int rate=8;
int m,n,q,spt,a[N][N],b[500005];
int sp[12000005],Tong[N][N][1001];
int S[ 12000005];
struct Node_t{int l,r,st,ed;}Tr[500005*rate];

struct Solve1_t{
int Sum,Limit,Num,x1,y1,x2,y2,h,Lt;
void input(){
spt=0;
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
memset(Tong,0,sizeof(Tong));
int i,j,k;
for (i=1;i<=m;i++)
for (j=1;j<=n;j++){
if (i+j==2) {Tong[i][j][a[1][1]]++;continue;}
if (i>1){
for (k=1;k<=1000;k++)
Tong[i][j][k]=Tong[i-1][j][k];
for (k=1;k<=j;k++)
Tong[i][j][a[i][k]]++;
}else{
for (k=1;k<=1000;k++)
Tong[i][j][k]=Tong[i][j-1][k];
for (k=1;k<=i;k++)
Tong[i][j][a[k][j]]++;
}
}
}

void solve(){
S[0]=0;
for (int i=1;i<=spt;i++) S[i]=S[i-1]+sp[i];
for (int i=0,j;i scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&h);
int Nt;
Sum=Num=0;
for (j=1000;j>=1;j–){
Nt=0;
Nt+=Tong[x2][y2][j];
Nt-=Tong[x1-1][y2][j];
Nt-=Tong[x2][y1-1][j];
Nt+=Tong[x1-1][y1-1][j];
Sum+=Nt*j;
Num+=Nt;
if (Sum>=h){
Num-=(Sum-h)/j;
printf("%dn",Num);
break;
}
}
if (Sum }
}
}Deal1;

struct Solve2_t{
int x1,y1,x2,y2,Num,h,Limit;
int Sum;

void input(){
spt=0;
for (int i=1;i<=n;i++)
scanf("%d",&b[i]);
}

void Union(Node_t &x,Node_t &y){
for (int i=x.st,j=y.st;i<=x.ed || j<=y.ed;)
if (i<=x.ed && (j>y.ed || sp[i] else sp[++spt]=sp[j++];
}

void build(int p,int l,int r){
Tr[p].l=l; Tr[p].r=r;
if (l==r){
Tr[p].st=Tr[p].ed=++spt;
sp[spt]=b[l];
}else{
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
Tr[p].st=spt+1;
Union(Tr[p*2],Tr[p*2+1]);
Tr[p].ed=spt;
}
S[Tr[p].ed]=sp[Tr[p].ed];
for (int i=Tr[p].ed-1;i>=Tr[p].st;i–)
S[i]=S[i+1]+sp[i];
}

void Try(int p){
if (y1<=Tr[p].l && Tr[p].r<=y2){
if (Limit>sp[Tr[p].ed]) return;
int l=Tr[p].st,r=Tr[p].ed,mid;
while (l mid=(l+r)/2;
if (sp[mid] else r=mid;
}
Sum+=S[l];
Num+=Tr[p].ed-l+1;
}else{
int mid=(Tr[p].l+Tr[p].r)/2;
if (y1<=mid) Try(p*2);
if (y2>mid) Try(p*2+1);
}
}

bool can(int tmp){
Limit=tmp;
Sum=Num=0;
Try(1);
if (Sum return true;
}

void solve(){
int l,r,mid;
for (int i=0;i scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&h);
l=1,r=1000;
while (l+1 mid=(l+r)/2;
if (can(mid)) l=mid;
else r=mid-1;
}
if (can(r)) l=r;
if (!can(l)) puts("Poor QLW");
else{
Num-=(Sum-h)/l;
printf("%dn",Num);
}
}
}
}Deal2;

int main(){
freopen("susu.in","r",stdin);
freopen("susu.out","w",stdout);
scanf("%d%d%d",&m,&n,&q);
if (m>1){
Deal1.input();
Deal1.solve();
}
else{
Deal2.input();
Deal2.build(1,1,n);
Deal2.solve();
}
return 0;
}