分类存档：默认分类

题意：

有N个数，每次从左至右选M个数，即[1..M]，[2..M+1]，…，[M-N+1..N]，选取每个区间的最大值和最小值。

解题分析：

明显的单调队列解决，复杂度O(N)

但是却跑了6000+MS。不知道那些500MS的怎么跑出来的。

code：

#include #define N 1000001
using namespace std;

int n,m,a[N],qf[N],qn[N];

void init(){
     scanf("%d%d",&n,&m);
     for (int i=1;i<=n;i++)
       scanf("%d",&a[i]);
}

void work1(){
     int head=1,tail=0;
     for (int i=1;i         while (head<=tail && qf[tail]>=a[i]) tail--;
         tail++;
         qf[tail]=a[i];
         qn[tail]=i;
     }
     for (int i=m;i<=n;i++){
         while (head<=tail && qf[tail]>=a[i]) tail--;
         tail++;
         qf[tail]=a[i];
         qn[tail]=i;
         while (qn[head]         printf("%d",qf[head]);
         if (i!=n) cout << " ";
     }
     cout << endl;
}

void work2(){
     int head=1,tail=0;
     for (int i=1;i         while (head<=tail && qf[tail]<=a[i]) tail--;
         tail++;
         qf[tail]=a[i];
         qn[tail]=i;
     }
     for (int i=m;i<=n;i++){
         while (head<=tail && qf[tail]<=a[i]) tail--;
         tail++;
         qf[tail]=a[i];
         qn[tail]=i;
         while (qn[head]         printf("%d",qf[head]);
         if (i!=n) cout << " ";
     }
     cout << endl;

}

int main(){
    init();
    work1();
    work2();
    return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=1823 题目是中文的。

题意：

给定一些点对(x,y)，和这些点对的权值。求满足(x1<=x<=x2 && y1<=y<=y2)的点里权值最大的一个。

由于小数点只有一个，所以把他*10就可以当整数处理。

解题思路：

标准的二维线段树的应用。建立二维线段树动态维护即可。

收获：

学会了二维线段树，但TLE了好几次。

究其原因，是我以为在#define里定义的max函数和真正的函数是一样的，但实际上是替换而已。

直接调用max(solve(xxxx),solve(xxxx))这样C++会计算两次。导致超时。以后max里不要调用函数。

要调用先用变量存起来。

code：

#include #define L(x) (x)<<1
#define R(x) ((x)<<1)|1
#define round(x) (int)((x)+0.5)
#define max(x,y) (x)>(y)?(x):(y)
struct atype{int l,r;} a[300];
struct btype{int l,r,max;} b[300][3000];

int m;

void swap(double &x,double &y){
     double t;
     t=x; x=y; y=t;
}

void buildy(int p,int x,int l,int r){
     b[x][p].l=l; b[x][p].r=r; b[x][p].max=-1;
     if (l       int mid=l+r>>1;
       buildy(L(p),x,l,mid);
       buildy(R(p),x,mid+1,r);
     }
}

void buildx(int p,int l,int r){
     a[p].l=l; a[p].r=r;
     buildy(1,p,0,1000);
     if (l       int mid=l+r>>1;
       buildx(L(p),l,mid);
       buildx(R(p),mid+1,r);
     }
}

void inserty(int p,int x,int y,int data){
     if (b[x][p].l==b[x][p].r){
       b[x][p].max=max(b[x][p].max,data);
       return;
     }
     if (b[x][p].max==-1){
       b[x][L(p)].max=-1;
       b[x][R(p)].max=-1;
     }
     int mid=b[x][p].l+b[x][p].r>>1;
     if (y<=mid) inserty(L(p),x,y,data);
            else inserty(R(p),x,y,data);
     b[x][p].max=max(b[x][p].max,data);
}

void insertx(int p,int x,int y,int data){
     inserty(1,p,y,data);
     if (a[p].l==a[p].r) return;
     int mid=a[p].l+a[p].r>>1;
     if (x<=mid) insertx(L(p),x,y,data);
            else insertx(R(p),x,y,data);
}

int solvey(int p,int x,int y1,int y2){
    if (y2    if (b[x][p].l>=y1 && y2>=b[x][p].r) return b[x][p].max;
    int t1=solvey(L(p),x,y1,y2),t2=solvey(R(p),x,y1,y2);
    return max(t1,t2);
}

int solvex(int p,int x1,int x2,int y1,int y2){
    if (x1>a[p].r || x2    if (a[p].l>=x1 && x2>=a[p].r) return solvey(1,p,y1,y2);
    int t1=solvex(L(p),x1,x2,y1,y2),t2=solvex(R(p),x1,x2,y1,y2);
    return max(t1,t2);
}

void work(){
     for (int i=1;i<=m;i++){
         char operate;
         scanf("%c",&operate);
         if (operate==’I’){
           int height;
           double A,L;
           scanf("%d %lf %lfn",&height,&A,&L);
           insertx(1,height,round(A*10),round(L*10));
         }
         else{
           double h1,h2,a1,a2;
           scanf("%lf %lf %lf %lfn",&h1,&h2,&a1,&a2);
           if (h1>h2) swap(h1,h2);
           if (a1>a2) swap(a1,a2);
           int ans=solvex(1,round(h1),round(h2),round(a1*10),round(a2*10));
           if (ans==-1) printf("-1n");
                   else printf("%d.%dn",ans/10,ans%10);
         }
     }
}

void init(){
     for (int i=0;i<300;i++) b[i][1].max=-1;
}

int main(){
    buildx(1,100,200);
    for (;;){
        scanf("%dn",&m);
        if (m==0) break;
        init();
        work();
    }
    return 0;
}