0_0_23257390_17259.cpp: In function 'int update(int, int)':
0_0_23257390_17259.cpp:32:35: error: expected '}' at end of input
tree[tot].num=tree[root].num+1;//此时新创立的根节点的值等于上一个创立的树的根节点的值+1(因为每次只更新一个位置的值+1 因此总体也只+1 int left=1;int right=tot_num;//对上一颗树进行扫描 寻找需要更改增加的节点和无需更改的节点 while(left<right) { int mid=(left+right)>>1; if(x<=mid)//如果需要更改的值在左子树 { tree[now].right=tree[root].right;//此时新创立的节点的右子树就是此时扫描点的右子树 因为无需更改 直接将新创立节点的右子树指向扫描点的右子树 这也是主席树精华所在(个人认为) 很大程度上节约了空间 tree[now].left=++tot;//在当前的新节点上对左子树创立一个新节点 此时当前新节点已经完成 递归进入下一个新节点 root=tree[root].left;//扫描的点进行与上面同样的动作 往左扫描 now=tot;//此时的新节点变为了当前新节点的左节点 然后递归 right=mid;//二分步骤 } else { //类比左子树 tree[now].left=tree[root].left; tree[now].right=++tot; root=tree[root].right; now=tot; left=mid+1; } tree[now].num=tree[root].num+1;//对于新节点 即已经判断需要更改的节点在此区间 对其值进行更新 同样只需要+1 } return tmp;//返回之前记录的这个新创立的线段树的根节点}int query(int qleft,int qright,int k)//qleft为1~i这个线段树的根节点 qright为1~j的 (假设查询【i~j】区间)(i~j区间的线段树可表示为 线段树j-1减去线段树((i-1)-1)类比树状数组思想 而接下来的操作都是在两个线段树的相加减基础上的 之所以可以相加减 因为主席树里的线段树保证了结构相同的特点{ int left=1;int right=tot_num; while(left<right) { int mid=(left+right)>>1; if(tree[tree[qright].left].num-tree[tree[qleft].left].num>=k)//如果左子树的值大于等于 说明第k大的树在左子树中 { qleft=tree[qleft].left; qright=tree[qright].left; right=mid; } else//否则在右子树中 { left=mid+1; k-=(tree[tree[qright].left].num-tree[tree[qleft].left].num); qleft=tree[qleft].right; qright=tree[qright].right; } } return left;//对相减的线段树进行扫描寻找第k大的值 直到找到 返回的值注意不是数本身 是第k大的数的下标 之后再在已经排序的c数组里得到这个数的具体值}int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&b[i]); c[i]=b[i]; } sort(c+1,c+1+n);//先排序 tot_num=unique(c+1,c+n+1)-c-1;//后去重 这里之所以不用set容器实现 因为操作运算符里“-"不允许对其地址的加减操作(差不多这么解释。。 迭代器的东西跟操作运算符不是太懂 本来写的lower_bound()-set.begin()就是会报错运算符) t[0]=build(1,tot_num);//先是基础树(num都为0) for(int i=1;i<=n;i++) { t[i]=update(t[i-1],lower_bound(c+1,c+tot_num+1,b[i])-c);//每个树在上一个树的基础上进行更新和扫描 } while(m--) { int l,r,k; scanf("%d%d%d",&l,&r,&k); printf("%d\n",c[query(t[l-1],t[r],k)]);//最后query返回的是c数组位置的下标索引 }}
^
|
