zoj 月赛的时候没有解出来，当时以为是二维线段树，由于二维的一道都没写过，所以这题被我放弃了，后来看了别人的解题报告，原来是一维的。。。
先按高度给line从小到大排序，然后按顺序插入木板，后面可以覆盖前面的，然后再在线段树上插入砖块，用一个num域来表示这一段有多少砖块，然后最后统计的时候把所有的标记下传到叶子节点再算就成。由于好久没写线段树，写的时候思维有点混乱，并且使用了复制粘贴，导致两句代码有问题，一直没有发现，一共WA了7次（-_-|||）
1 #include<iostream>
2 #include<algorithm>
3 #define MAXN 100010
4 using namespace std;
5 struct NODE
6 {
7 int l,r;
8 int ID,num;// 分别记录第cnt条木板 和 砖块数量
9 }tree[MAXN*12];
10 struct Board
11 {
12 int l,r,h,ID;
13 };
14 struct Brick
15 {
16 int l,r;
17 };
18 Brick bri[MAXN];
19 Board ban[MAXN];
20 int x[MAXN*4];
21 int n,m,len;
22 long long ans[MAXN];
23
24 bool compare( const Board &a, const Board &b )
25 {
26 return a.h<b.h;
27 }
28
29 int find( int n )
30 {
31 int l=0,r=len-1,mid;
32 while( l<=r )
33 {
34 mid=(l+r)>>1;
35 if( x[mid]==n )return mid;
36 else if( x[mid]<n )l=mid+1;
37 else r=mid-1;
38 }
39 }
40
41 void make_tree( int v, int l, int r )
42 {
43 int mid;
44 tree[v].l=l,tree[v].r=r,tree[v].ID=0,tree[v].num=0;
45 if( l+1 != r )
46 {
47 mid=(l+r)>>1;
48 make_tree( v<<1, l, mid );
49 make_tree( (v<<1)+1, mid, r );
50 }
51 }
52
53 void lisanhua( )
54 {
55 int i,k=len;
56 sort( x, x+len );
57 len=1;
58 for( i=1; i<k; i++ )
59 if( x[i] != x[i-1] )x[len++]=x[i];
60 for( i=1; i<=n; i++ )
61 {
62 bri[i].l=find( bri[i].l );
63 bri[i].r=find( bri[i].r );
64 }
65 for( i=1; i<=m; i++ )
66 {
67 ban[i].l=find( ban[i].l );
68 ban[i].r=find( ban[i].r );
69 }
70 }
71
72 void insertboard( int v, int l, int r, int ID )
73 {
74 int mid;
75 if( tree[v].l==l && tree[v].r==r )
76 {
77 tree[v].ID=ID;
78 return ;
79 }
80 if( tree[v].ID )
81 {
82 if( tree[v].l+1 != tree[v].r )
83 {
84 tree[v<<1].ID=tree[v].ID;
85 tree[(v<<1)+1].ID=tree[v].ID;
86 tree[v].ID=0;
87 }
88 }
89 mid=(tree[v].l+tree[v].r)>>1;
90 if( r<=mid )insertboard( v<<1, l, r, ID );
91 else if( l>=mid )insertboard( (v<<1)+1, l, r, ID );
92 else
93 {
94 insertboard( v<<1, l, mid, ID );
95 insertboard( (v<<1)+1, mid, r, ID );
96 }
97 }
98
99 void insertbrick( int v, int l, int r )
100 {
101 int mid;
102 if( tree[v].l==l && tree[v].r==r )
103 {
104 tree[v].num++;
105 //if( tree[v].l+1==tree[v].r )return ;
106 //tree[v<<1].num+=tree[v].num;
107 //tree[(v<<1)+1].num+=tree[v].num;
108 //tree[v].num=0;
109 return ;
110 }
111 mid=(tree[v].l+tree[v].r)>>1;
112 if( r<=mid )insertbrick( v<<1, l, r );
113 else if( l>=mid )insertbrick( (v<<1)+1, l, r );
114 else
115 {
116 insertbrick( v<<1, l, mid );
117 insertbrick( (v<<1)+1, mid, r );
118 }
119 }
120
121 void query( int v, int l, int r )
122 {
123 int mid;
124 if( tree[v].l+1==tree[v].r )
125 {
126 ans[tree[v].ID]=ans[tree[v].ID]+(long long)(x[tree[v].r]-x[tree[v].l])*(long long)tree[v].num;
127 return ;
128 }
129 if( tree[v].ID )
130 {
131 tree[v<<1].ID=tree[v].ID;
132 tree[(v<<1)+1].ID=tree[v].ID;
133 tree[v].ID=0;
134 }
135 if( tree[v].num )
136 {
137 tree[v<<1].num+=tree[v].num;
138 tree[(v<<1)+1].num+=tree[v].num;
139 tree[v].num=0;
140 }
141 mid=(tree[v].l+tree[v].r)>>1;
142 if( r<=mid )query( v<<1, l, r );
143 else if( l>=mid ) query( (v<<1)+1, l, r );
144 else
145 {
146 query( v<<1, l, mid );
147 query( (v<<1)+1, mid, r );
148 }
149 }
150
151 void solve( )
152 {
153 int i;
154 sort( ban+1, ban+m+1, compare );
155 make_tree( 1, 0, len-1 );
156 for( i=1; i<=m; i++ )
157 insertboard( 1, ban[i].l, ban[i].r, ban[i].ID );
158 for( i=1; i<=n; i++ )
159 insertbrick( 1, bri[i].l, bri[i].r );
160 memset( ans, 0, sizeof(ans) );
161 query( 1, 0, len-1 );
162 for( i=1; i<=m; i++ )
163 printf("%lld\n",ans[i]);
164 printf("\n");
165 }
166
167 int main( )
168 {
169 int i;
170 while( scanf("%d%d",&n,&m) != EOF )
171 {
172 len=0;
173 for( i=1; i<=n; i++ )
174 {
175 scanf("%d%d",&bri[i].l,&bri[i].r);
176 x[len++]=bri[i].l;
177 x[len++]=bri[i].r;
178 }
179 for( i=1; i<=m; i++ )
180 {
181 scanf("%d%d%d",&ban[i].l,&ban[i].r,&ban[i].h);
182 x[len++]=ban[i].l;
183 x[len++]=ban[i].r;
184 ban[i].ID=i;
185 }
186 lisanhua( );
187 solve( );
188 }
189 return 0;
190 }