8.9考试总结

· · 个人记录

T1

发现答案要求的是 m 之前有多少个，所以考虑到树状数组。

发现是单点修改，区间查询的模版。

T2

用线段树维护乘积。

把乘的节点变为 m，除就改为 1。

T3

发现这道题把 x 排序后，就是求 y 的最大上升子序列和。

用树状数组维护区间最值即可。

//Code by hhy
#include<bits/stdc++.h>
//#define int long long
#define ull unsigned long long
#define ll long long
using namespace std ;
const int kMaxN = 1e5 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
    int u , w ;
};
struct Edgeve
{
    int v , w ;
};
struct node
{
  int x , y , w ;
}a[kMaxN] ;
int n , m , k , len ;
int b[kMaxN] , dp[kMaxN] , c[kMaxN] ;
inline ll ksm(ll a , ll b)
{
    ll mul = 1 ;
    while(b)
    {
        if(b & 1) mul *= a , mul %= MOD ;
        a *= a ;
        a %= MOD ;
        b >>= 1 ;
    }
    return mul ;
}
int lowbit(int x)
{
    return (x & (-x)) ;
}
void update(int x , int k)
{
    while(x <= kMaxN - 1)
    {
        c[x] = max(c[x] , k) ;
        x += lowbit(x) ;
    }
}
int query(int x)
{
    int ans = 0 ;
    while(x)
    {
        ans = max(ans , c[x]) ;
        x -= lowbit(x) ;
    }
    return ans ;
}
bool cmp(node x , node y)
{
    if(x.x != y.x) return x.x < y.x ;
    return x.y < y.y ;
}
void work()
{
    cin >> n >> m >> k ;
    for( int i = 1 ; i <= k ; i++ )
    {
        cin >> a[i].x >> a[i].y >> a[i].w ;
        b[i] = a[i].y ;
    }
    sort(a + 1 , a + k + 1 , cmp) ;
    sort(b + 1 , b + k + 1) ;
    len = unique(b + 1 , b + k + 1) - (b + 1) ;
    for( int i = 1 ; i <= k ; i++ )
    {
        a[i].y = lower_bound(b + 1 , b + len + 1 , a[i].y) - b ;
    }
    int maxn = 0 ;
    for( int i = 1 ; i <= k ; i++ )
    {
        dp[i] = query(a[i].y) + a[i].w ;
        update(a[i].y , dp[i]) ;
        maxn = max(maxn , dp[i]) ;
    }
    cout << maxn ; 
}
signed main()
{
//  freopen(".in" , "r" , stdin) ;
//  freopen(".out" , "w" , stdout) ;
    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}

T4

发现第一个提问就是 lazy 求最大值。

对于第二个提问，用线段树维护区间最小值，对于其他的，用分治的思想，从最小点两边开始找次小值，用优先队列维护即可。

//Code by hhy
#include<bits/stdc++.h>
//#define int long long
#define ull unsigned long long
#define ll long long
using namespace std ;
const int kMaxN = 5e5 + 5 , MOD = 998244353 , INF = 1e9 ;
struct Edgepr
{
    int u , w ;
};
struct Edgeve
{
    int v , w ;
};
struct node
{
  int l , r , w , p ;
  bool operator < (const node &a) const
  {
    return w > a.w ;
    }
};
int n , m ; 
ll minn[kMaxN << 2] , pos[kMaxN << 2] , lazy[kMaxN << 2] , w[kMaxN] ;
vector<int> vec ;
priority_queue<node> q ;
#define lson(x) x << 1 
#define rson(x) (x << 1) | 1 
void push_up(int k)
{
    minn[k] = INF ;
    if(minn[lson(k)] < minn[k])
    {
        minn[k] = minn[lson(k)] ;
        pos[k] = pos[lson(k)] ;
    }
    if(minn[rson(k)] < minn[k])
    {
        minn[k] = minn[rson(k)] ;
        pos[k] = pos[rson(k)] ;
    }
}
void build(int k , int l , int r)
{
    if(l == r)
    {
        minn[k] = w[l] ;
        pos[k] = l ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    build(lson(k) , l , mid) ;
    build(rson(k) , mid + 1 , r) ;
    push_up(k) ;
}
void push_down(int k)
{
    if(lazy[k] == 0) return ;
    lazy[lson(k)] = max(lazy[lson(k)] , lazy[k]) ;
    lazy[rson(k)] = max(lazy[rson(k)] , lazy[k]) ;
    minn[lson(k)] = max(minn[lson(k)] , lazy[k]) ;
    minn[rson(k)] = max(minn[rson(k)] , lazy[k]) ;
    lazy[k] = 0 ;
}
void update(int L , int R , ll v , int k , int l , int r)
{
    if(l >= L && r <= R)
    {
        minn[k] = max(v , minn[k]) ;
        lazy[k] = max(v , lazy[k]) ;
        return ;
    }
    push_down(k) ;
    int mid = (l + r) >> 1 ;
    if(L <= mid)
    {
        update(L , R , v , lson(k) , l , mid) ;
    }
    if(R > mid)
    {
        update(L , R , v , rson(k) , mid + 1 , r) ;
    }
    push_up(k) ;
}
pair<int , int> query(int L , int R , int k , int l , int r)
{
    if(L <= l && r <= R)
    {
        return {minn[k] , pos[k]} ;
    }
    if(L > R)
    {
        return {INF , 0} ;
    }
    push_down(k) ;
    pair<int , int> res = {INF , 0} ;
    int mid = (l + r) >> 1 ;
    if(L <= mid)
    {
        pair<int , int> p = query(L , R , lson(k) , l , mid) ;
        if(p.first < res.first)
        {
            res = p ;
        }
    }
    if(R > mid)
    {
        pair<int , int> p = query(L , R , rson(k) , mid + 1 , r) ;
        if(p.first < res.first)
        {
            res = p ;
        }
    }
    return res ;
}
void work()
{
    cin >> n ;
    for( int i = 1 ; i <= n ; i++ ) cin >> w[i] ;
    build(1 , 1 , n) ;
    cin >> m ;
    for( int i = 1 ; i <= m ; i++ )
    {
        int op ;
        cin >> op ;
        if(op == 1)
        {
            int l , r , k ;
            cin >> l >> r >> k ;
            update(l , r , k , 1 , 1 , n) ;
        }
        else
        {
            int l , r , k , x ;
            cin >> l >> r >> k >> x ;
            vec.clear() ;
            while(!q.empty()) q.pop() ;
            pair<int , int> p = query(l , r , 1 , 1 , n) ;
            q.push({l , r , p.first , p.second}) ;
            while(!q.empty())
            {
                node u = q.top() ;
                q.pop() ;
                if(u.w >= k) continue ;
                vec.push_back(u.w) ;
                pair<int , int> p1 = query(u.l , u.p - 1 , 1 , 1 , n) ;
                pair<int , int> p2 = query(u.p + 1 , u.r , 1 , 1 , n) ;
                q.push({u.l , u.p - 1 , p1.first , p1.second}) ;
                q.push({u.p + 1 , u.r , p2.first , p2.second}) ;
                if(vec.size() == x) break ;
            }
            if(vec.size() != x) cout << "-1\n" ;
            else
            {
                sort(vec.begin() , vec.end()) ;
                for( int i = 0 ; i < x ; i++ ) cout << vec[i] << " " ;
                cout << "\n" ;
            }
        }
    }
}
signed main()
{
//  freopen(".in" , "r" , stdin) ;
//  freopen(".out" , "w" , stdout) ;
    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
//  cin >> t ;
  while(t--) work() ;
  return 0 ;
}