一直WA，找不到错了……谁能提供几组强力数组也好啊~~
方法：
1.以x坐标排序为扫描线，n个人也按照x坐标排序
2.每次，求相邻的两条扫描线之间的面积；
3.对于相邻的两条扫描线之间，用离散化y坐标的线段树确定矩形的高，两条扫描线之间的距离为宽

代码：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 60000
#define M 30011
struct node{
    int x1,x2,y1,y2;
    int s;
};
    
int tree[N*5];
node p[M];
int x[3*M];
int y[3*M];
int n,m;
int pi[100];
long long ans;
int px,py;

bool cmp(node a,node b){
    return a.x1 < b.x1 || (a.x1 == b.x1 && a.x2 < b.x2);
}
    
bool cmp1(int a,int b){
    return a<b;
}
    
void insert(int l,int r,int s,int t,int k,int pos){
    //cout<<y[l]<<" "<<y[r]<<" "<<s<<" "<<t<<endl;
    if (tree[pos] >= k) return;
    if (y[l] == s && y[r] == t && tree[pos] == -1) {
        tree[pos] = k;
        return;
    }    
    if (r - l <= 1) {
        tree[pos] = max(tree[pos],k);
        return;
    }
        
    if (tree[pos] != 0){
        tree[pos<<1] = tree[(pos<<1)+1] = tree[pos];
        tree[pos] = 0;
    }    
    int mid = (l+r)>>1;
    if (t <= y[mid]) insert(l,mid,s,t,k,pos<<1);
    else if (y[mid] <= s) insert(mid,r,s,t,k,(pos<<1)+1);
    else{
        insert(l,mid,s,y[mid],k,pos<<1);
        insert(mid,r,y[mid],t,k,(pos<<1)+1);
    }    
}
    
long long getArea(int l,int r,int pos){
    long long res = 0;
    if (tree[pos] == -1) return 0;
    else if (r - l == 1 || tree[pos] > 0) {
        res = (long long)tree[pos]*(y[r]-y[l]);
    }    
    else if (tree[pos] == 0){
        int mid = (l+r)>>1;
        res = getArea(l,mid,pos<<1)+getArea(mid,r,(pos<<1)+1);
    }
    return res;    
}
    
int main(){
    int T,index = 0;
    scanf("%d",&T);
    while (T--){
        px = 0;
        py = 0;
        scanf("%d %d",&n,&m);
        for (int i=1 ;i<=m ;++i) scanf("%d",pi+i);
        for (int i=0 ;i<n ;++i) {
            scanf("%d %d %d %d %d",&p[i].x1,&p[i].y1,&p[i].x2,&p[i].y2,&p[i].s);
            x[px++] = p[i].x1; x[px++] = p[i].x2;
            y[py++] = p[i].y1; y[py++] = p[i].y2;
        }
        ans = 0;
        sort(p,p+n,cmp);    
        sort(x,x+px,cmp1);
        sort(y,y+py,cmp1);
        int l = x[0],r;
        int j = 0;
        --py;
        for (int i=1 ;i<px; ++i){
            r = x[i];
            if (l == r) continue;
            while (j < n && p[j].x2 <= l) ++j;
            tree[1] = -1;
            int w = r-l;
            int d = j;
            while (d < n && p[d].x1 <= l && r <= p[d].x2) {
                //cout<<p[d].y1<<" "<<p[d].y2<<endl;
                insert(0,py,p[d].y1,p[d].y2,pi[p[d].s],1);
                ++d;
            }    
            long long tmp = getArea(0,py,1);
            //cout<<tmp<<endl<<"end..."<<endl;
            ans += tmp*w;   
            l = r;
        }      
        printf("Case %d: %I64d\n",++index,ans);
    }    
    return 0;
}    

• 不同价值的长度怎么处理的?我MLE- -| (3130) twilight 2009-09-12 17:39:00
  • Re:不同价值的长度怎么处理的?我MLE- -| (9) sybil_0603 2009-09-12 17:43:57
    • Sample 2 正方形被另一个价值大的盖掉的一部分怎么处理呢?离散化+线段树这个大的框架肯定是的 (13) twilight 2009-09-12 17:46:16
      • Re:Sample 2 正方形被另一个价值大的盖掉的一部分怎么处理呢?离散化+线段树这个大的框架肯定是的 (27) cuiaoxiang 2009-09-12 18:14:44
        • Re:Sample 2 正方形被另一个价值大的盖掉的一部分怎么处理呢?离散化+线段树这个大的框架肯定是的 (14) mabaochang 2009-09-12 18:22:38
          • 我线段树segment fault (48) zfacmilan 2009-09-12 19:30:26
            • 我一直Judge Internal Error (54) twilight 2009-09-12 22:25:34
        • 好像有点明白了 (54) twilight 2009-09-12 19:35:43
          • 不太懂 (6) zfacmilan 2009-09-12 20:20:36
            • 分层之后就是普通的离散化+线段树求面积并了 (10) twilight 2009-09-12 21:02:57
              • Re:分层之后就是普通的离散化+线段树求面积并了 (58) zfacmilan 2009-09-12 21:29:00
                • 上面说了,分层是一种思想,处理的时候不用那么复杂 (196) twilight 2009-09-12 21:56:34
                  • Re:上面说了,分层是一种思想,处理的时候不用那么复杂 (18) lysaitl 2009-09-12 22:04:11
                    • 自己画个图就好了 (0) twilight 2009-09-12 22:07:00
                      • Re:自己画个图就好了 (14) lysaitl 2009-09-12 22:08:26