NC208615. 区间第k大
描述
输入描述
一个数n，表示数列A长度为n。
接下来一行n个数表示数列A。
下一行接一个数m表示有m个询问。
对于询问:格式为，1表示询问，l、r表示询问的区间，k表示第k大。
对于修改:格式为，2表示修改，pos表示修改的位置，x表示修改为x。
输出描述
对于每个询问输出一个数表示答案。
示例1
输入:
5 1 2 3 4 5 4 1 1 3 2 2 1 3 1 1 3 1 1 4 5 2
输出:
2 3 4
C++14(g++5.4) 解法, 执行用时: 791ms, 内存消耗: 5208K, 提交时间: 2020-07-06 11:35:56
#include<bits/stdc++.h>
using namespace std;
class tree{
public:
int l,r,maxn,p;//p存最大点坐标
};
class tree tt[400100];
int p[100100];
void buildtree(int node,int l,int r){
if(l==r){
tt[node].l=l,tt[node].r=r;
tt[node].maxn=p[l];
tt[node].p=l;
return;
}
else{
int mid=(l+r)>>1;
buildtree(node<<1,l,mid);
buildtree((node<<1)+1,mid+1,r);
tt[node].l=l,tt[node].r=r;
tt[node].maxn=max(tt[node<<1].maxn,tt[(node<<1)+1].maxn);
if(tt[node].maxn==tt[node<<1].maxn)tt[node].p=tt[node<<1].p;
else tt[node].p=tt[(node<<1)+1].p;
}
}
void updatatree(int pos,int node,int x){
if(tt[node].l==tt[node].r){
tt[node].maxn=x;
return;
}
int mid=(tt[node].l+tt[node].r)>>1;
if(pos<=mid)updatatree(pos,node<<1,x);
if(pos>mid)updatatree(pos,(node<<1)+1,x);
tt[node].maxn=max(tt[node<<1].maxn,tt[(node<<1)+1].maxn);
if(tt[node].maxn==tt[node<<1].maxn)tt[node].p=tt[node<<1].p;
else tt[node].p=tt[(node<<1)+1].p;
}
class tree findmax(int node,int l,int r){
if(tt[node].l>=l&&tt[node].r<=r)
return tt[node];
int mid=(tt[node].l+tt[node].r)>>1;
class tree max1;
max1.maxn=-1;
if(l<=mid)max1=findmax(node<<1,l,r);
if(r>mid)if(max1.maxn<findmax((node<<1)+1,l,r).maxn){
max1=findmax((node<<1)+1,l,r);
}
return max1;
}
int main(){
int n,ww,pos,l,r,k,y,x;
class tree f;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&p[i]);
buildtree(1,1,n);
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&ww);
if(ww==1){
scanf("%d%d%d",&l,&r,&k);
if(k==1){
f=findmax(1,l,r);
printf("%d\n",f.maxn);
}
else{
f=findmax(1,l,r);
x=f.maxn,y=f.p;
updatatree(f.p,1,-1);
f=findmax(1,l,r);
printf("%d\n",f.maxn);
updatatree(y,1,x);
}
}
else{
scanf("%d%d",&pos,&k);
updatatree(pos,1,k);
}
}
}
C++11(clang++ 3.9) 解法, 执行用时: 192ms, 内存消耗: 4832K, 提交时间: 2020-07-05 14:43:27
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
struct node{
int val,p;
bool operator < (const node& t)const {
return val < t.val;
}
};
node tr[maxn * 4];
#define ls o<<1
#define rs o<<1|1
#define mid (l+r)/2
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
void up(int o,int l,int r,int p,int val)
{
if(l == r)
{
tr[o].val = val;
tr[o].p = l;
return ;
}
if(p <= mid)up(lson,p,val);
else up(rson,p,val);
if(tr[ls] < tr[rs])tr[o] = tr[rs];
else tr[o] = tr[ls];
}
node qu(int o,int l,int r,int L,int R)
{
if(l >= L && r <= R)return tr[o];
node ans = node{-1000000000,0};
if(L <= mid)
{
node tmp = qu(lson,L,R);
if(ans < tmp)ans = tmp;
}
if(R > mid)
{
node tmp = qu(rson,L,R);
if(ans < tmp)ans = tmp;
}
return ans;
}
int main()
{
int n,x;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
up(1,1,n,i,x);
}
int q;
scanf("%d",&q);
while(q--)
{
int op,l,r,k;
scanf("%d",&op);
if(op == 1)
{
scanf("%d%d%d",&l,&r,&k);
node ans = qu(1,1,n,l,r);
if(k == 1)printf("%d\n",ans.val);
else {
up(1,1,n,ans.p,-1);
printf("%d\n",qu(1,1,n,l,r).val);
up(1,1,n,ans.p,ans.val);
}
}
else
{
scanf("%d%d",&l,&r);
up(1,1,n,l,r);
}
}
}