题目链接：
hdu 4866
题目大意：
给出n条直线，每次查询给出一个x，求这个x位置上方的前k个线段的高度之和。
题目分析：首先对高度进行离散化建立主席树，将每条直线对应为两个点，左端点+1,右端点-1，然后每个点建一个线段树，，然后每次查询对于一个x，只需要二分查找找到时序点，然后找到线段数量为k的最左的前缀即可。 AC代码：;LL;const int MAXN=200005;const int M=MAXN*20;int root[MAXN];struct LINE{int x, d, id;} line[MAXN];int y[MAXN], ind[MAXN], to[MAXN],num_trees;int i, j, cnt, n, m, x, p, L, R, D, X, A, B, C, k;bool cmp(LINE x1,LINE x2){return x1.x<x2.x;}bool cmp2(int a,int b){return y[a]<y[b];}struct Tree{int l,r,num;LL val;}tree[5000007];void build ( int &u , int l , int r ){u = ++num_trees;tree[u].num = tree[u].val = 0;if ( l == r ) return;int mid = l+r>>1;build ( tree[u].l , l , mid );build ( tree[u].r , mid+1 , r );}void update ( int p , int &u , int l , int r , int x , int v , int z ){u = ++num_trees;tree[u] = tree[p];tree[u].num += v;tree[u].val += z;if ( l == r) return;int mid = l+r>>1;if ( x > mid ) update ( tree[p].r , tree[u].r , mid+1 , r , x , v , z );else update ( tree[p].l , tree[u].l , l , mid , x , v , z );}LL query ( int u , int l , int r , int k ){if ( k == 0 ) return 0;if ( l == r ) return tree[u].val;int mid = l+r>>1;if ( tree[tree[u].l].num >= k ) return query ( tree[u].l , l , mid , k );else return tree[tree[u].l].val + query ( tree[u].r , mid+1 , r , k-tree[tree[u].l].num );}int bsearch ( int x ){int l=1,r=cnt,mid;while ( l != r ){mid = (l+r+1)>>1;if ( line[mid].x <= x ) l = mid;else r = mid-1;}return l;}int main(){while(~scanf(“%d%d%d%d”,&n,&m,&x,&p)){cnt=0;num_trees=0;for(i=1;i<=n;i++){scanf(“%d%d%d”,&L,&R,&D);y[i]=D;ind[i]=i;line[++cnt].x=L, line[cnt].d=D, line[cnt].id=i;line[++cnt].x=R+1, line[cnt].d=-D, line[cnt].id=i;}sort(line+1,line+cnt+1,cmp);sort(ind+1,ind+n+1,cmp2);for(i=1;i<=n;i++) to[ind[i]]=i;build ( root[0] , 1 , n );for(i=1;i<=cnt;i++)if ( line[i].d> 0 )update ( root[i-1] , root[i] , 1 , n , to[line[i].id] , 1 , line[i].d );elseupdate ( root[i-1] , root[i] , 1 , n , to[line[i].id] , -1 , line[i].d );LL pre=1, ret;for(i=1;i<=m;i++){scanf(“%d%d%d%d”,&X,&A,&B,&C);k=(pre%C*A%C+B)%C;int tt = bsearch ( X );ret = query ( root[tt] , 1 , n , k );if(pre>p) ret*=2;pre=ret;printf(“%I64d\n”,ret);}}return 0;}
愚者用肉体监视心灵，智者用心灵监视肉体
