首页 > 其他分享 >HDU - 5649 线段树+区间二分答案 (好题)

HDU - 5649 线段树+区间二分答案 (好题)

时间:2023-04-24 22:36:41浏览次数:63  
标签:rt HDU int memset 好题 mid 5649 line sizeof


DZY has a sequence a[1…n]. It is a permutation of integers 1∼n.

Now he wants to perform two types of operations:

0lr: Sort a[l…r] in increasing order.

1lr: Sort a[l…r] in decreasing order.

After doing all the operations, he will tell you a position k, and ask you the value of a[k].
Input
First line contains t, denoting the number of testcases.

t testcases follow. For each testcase:

First line contains n,m. m is the number of operations.

Second line contains n space-separated integers a[1],a[2],⋯,a[n], the initial sequence. We ensure that it is a permutation of 1∼n.

Then m lines follow. In each line there are three integers opt,l,r to indicate an operation.

Last line contains k.

(1≤t≤50,1≤n,m≤100000,1≤k≤n,1≤l≤r≤n,opt∈{0,1}. Sum of n in all testcases does not exceed 150000. Sum of m in all testcases does not exceed 150000)
Output
For each testcase, output one line - the value of a[k] after performing all m operations.
Sample Input
1
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
Sample Output
5

Hint
1 6 2 5 3 4 -> [1 2 5 6] 3 4 -> 1 2 [6 5 4 3] -> 1 [2 5 6] 4 3. At last HDU - 5649  线段树+区间二分答案 (好题)_线段树.

这次题目之前我们数据结构专题出过,所以比赛时候就直接交了;
考虑朴素算法:
每次对区间进行 sort,假设平均复杂度 NlogN
算上操作次数t. TLE是肯定的;
思路:
考虑用线段树进行维护,我们可以将大于 mid的设为1,小于mid 设为0 ,那么升序的时候将后面>mid设为1;降序则将前面设为1.每次二分答案,如果查询 [k,k]区间==1,说明在左区间;反之在右区间;

#include<bits/stdc++.h>
 using namespace std;
const int maxn = 2e5+7;
int lazy[maxn<<2];
int s[maxn<<2];
int a[maxn];
int op[maxn];
int l[maxn];
int r[maxn];
int n,k;
int tot;

void pushDown( int rt , int L , int R ){
    if( lazy[rt] != -1 ){
        int mid = ( L + R ) >> 1 ;
        s[rt<<1] = ( mid - L + 1 ) * lazy[rt] ;
        s[rt<<1|1] = ( R - mid ) * lazy[rt];
        lazy[rt<<1] = lazy[rt];
        lazy[rt<<1|1] = lazy[rt];
        lazy[rt] = -1;
    }
    return ;
}


void pushUp( int rt ){
    s[rt] = s[rt<<1] + s[rt<<1|1];
    return ;
}

void build( int l , int r , int rt , int v ){
    lazy[rt] = -1;
    if( l == r ){
        s[rt] =  ( a[l] > v ) ;
        return ; 
    }
    int mid = ( l + r ) >> 1 ;
    build( l , mid , rt << 1 , v );
    build( mid + 1 , r , rt << 1 | 1 , v);
    pushUp(rt);
}

void update( int L , int R , int v , int l , int r , int rt ){
    if( L <= l && R >= r ){
        s[rt] = v * ( r - l + 1 );
        lazy[rt] = v;
        return;
    }
    pushDown(rt,l,r);
    int mid = ( l + r ) >> 1;
    if( L <= mid ) update( L , R , v , l , mid , rt << 1 );
    if( R > mid ) update( L , R , v , mid + 1 , r , rt << 1 | 1);
    pushUp(rt);
}

int query( int L , int R , int l , int r , int rt ){
    if( L <= l && R >= r ){
        return s[rt];
    }
    pushDown(rt,l,r);
    int ans = 0 ;
    int mid = ( l + r ) >> 1;
    if( L <= mid ) ans += query( L , R , l , mid, rt << 1 );
    if( R > mid )  ans += query( L , R , mid + 1, r , rt << 1 | 1 );
    return ans ;
}

int main(){
	int t;
	cin>>t;
	while(t--){
	memset(s,0,sizeof(s));
	memset(lazy,0,sizeof(lazy));
	memset(a,0,sizeof(a));
	memset(op,0,sizeof(op));
	memset(l,0,sizeof(l));
	memset(r,0,sizeof(r));
    scanf("%d",&n);
	int m ;
    scanf("%d",&m);
    for( int i = 1 ; i <= n ; i++ ){
        scanf("%d",&a[i]);
    }
    
    for( int i = 0 ; i < m ; i++ ){
        scanf("%d%d%d",&op[i],&l[i],&r[i]);     
    }
    cin>>k;
    int li = 1 , ri = n ; 
    while( li < ri ){
        int mid = ( li + ri ) >> 1 ;
        build( 1 , n , 1 , mid );
        for( int i = 0 ; i < m ; i++ ){
            int L = l[i];
            int R = r[i];
            int c = query( L , R , 1 , n , 1 );
            update( L , R , 0 , 1 , n , 1 );
            if( op[i] ){  
                if( L <= L + c - 1 ){
                    update( L , L + c - 1 , 1 , 1, n , 1 );
                } 
            }else{
                if( R - c + 1 <= R ){
                    update( R - c + 1 , R , 1 , 1 , n , 1 );
                }
            }
        }
        if( query( k , k , 1 , n , 1 ) ){
            li = mid + 1 ;
        }else ri = mid  ;
    }
    printf("%d\n",li);
}
    return 0 ;
}


标签:rt,HDU,int,memset,好题,mid,5649,line,sizeof
From: https://blog.51cto.com/u_15657999/6221938

相关文章

  • 多校第六场 1011 hdu 5363Key Set(组合数学)
    题目链接:hdu5363题目大意:给出一个到n的自然数集合,问它有多少个子集,元素之和是偶数。题目分析:首先偶数不会导致集合的和的奇偶性发生变化;奇数会导致集合的和的奇偶性发生变化。我们设奇数m1个,偶数m2个。所以我们可以选取0~m1个偶数,但是只能选取偶数个奇数。那么偶数的方案数就是......
  • hdu 5441 长春区域赛网络赛 1005 Travel(并查集)
    题目链接:hdu5441题目大意:有一个n个点的无向图,给出m条边的边权,给出q次询问,每次给出一个值,求用到所有边权不大于这个值的边的情况下,能够互相到达的点对的个数(自己到自己不算)题目分析:首先我们对于边按照边权从小到大排序,对于询问按照值从小到大排序。枚举每次询问,从前到后扫描边,如果......
  • hdu 5442 长春区域赛网络赛 1006 Favorite Donut(后缀数组)
    题目链接:hdu5442题目大意:给出一个环,每颗珠子有一个甜度,选择第一个珠子和吃的方向,问得到的吃珠子的字符串的字典序最大的,如果有多个,选取位置最靠前的,如果还是多个,选择顺时针吃的。题目分析:-首先构造一个字符串,首先正着按环吃,那么就是字符串正着写两遍,连接在一起;中间用没有出现过的......
  • hdu 5446 长春区域赛网络赛1010 Unknown Treasure(lucas定理+中国剩余定理+移位乘法)
    题目链接:hdu5446题目大意:求出Cmn%M,M=p1⋅p2⋯pk题目分析:首先对于每个质数pi我们,我们可以利用Lucas定理求出Cmn%pi的值,Lucas定理如下:Cmn%p=Cm/pn/p⋅Cm%pn%p%p然后我们可以利用中国剩余定理求取最后答案:M=∏i=1kpi,Mi=M/piCmn%M=∑i=1kCmn%pi⋅Mi⋅inv[Mi]因为做乘法......
  • hdu 5444 长春区域赛网络赛 1008 Elven Postman(模拟)
    题目链接:hdu5444题目大意:给出一个序列,这个序列的第一个点是树的根节点,每次操作从当前点走到当前最靠右的每走过的点(点的序号越小越靠右),问将物品从根送到某个点的行进路线.题目分析:个人认为难在题意。。。构造出这个树之后,直接从目的地走回根节点就可以得到要求的路径。然后如何构......
  • HDU 5389 Zero Escape(DP + 滚动数组)
    ZeroEscapeTimeLimit:2000/1000MS(Java/Others)    MemoryLimit:131072/131072K(Java/Others)TotalSubmission(s):864    AcceptedSubmission(s):438ProblemDescriptionZeroEscape,isavisualnoveladventurevideogamedirectedbyKotar......
  • HDU1873 看病要排队
    E- 看病要排队TimeLimit:1000MS     MemoryLimit:32768KB     64bitIOFormat:%I64d&%I64uDescription看病要排队这个是地球人都知道的常识。不过经过细心的0068的观察,他发现了医院里排队还是有讲究的。0068所去的医院有三个医生(汗,这么......
  • HDU 1114 Piggy-Bank
    F- Piggy-BankTimeLimit:1000MS     MemoryLimit:32768KB     64bitIOFormat:%I64d&%I64uSubmit StatusDescriptionBeforeACMcandoanything,abudgetmustbepreparedandthenecessaryfinancialsupportobtained.Themaininc......
  • HDU 1869 六度分离
    六度分离TimeLimit:1000MS     MemoryLimit:32768KB     64bitIOFormat:%I64d&%I64uSubmit Status Practice HDU1869Description1967年,美国著名的社会学家斯坦利・米尔格兰姆提出了一个名为“小世界现象(smallworldphenom......
  • HDU 1527 取石子游戏(博弈论)
    取石子游戏TimeLimit:2000/1000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):3717    AcceptedSubmission(s):1868ProblemDescription有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有......