2019 Shaanxi provincial competition j-bit operation + greed

The main idea of the topic ：

Here you are. $n$ Intervals , You need to take a number from each interval . Make them rank with the largest .

Topic ideas ：

Start from the high position and try to set 1. then check Every interval .
I turn the question into : Find less than $R$ The largest of contains the current $ans$ Number of numbers $X$. then check It and $L$ The size of the relationship .

So from Interval existence problem Turn into : The most valuable question . At this time, you can also be greedy .

In this way, I still take two log, You need to add pruning at two places , Last time from T Optimize to 277ms

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
const int maxn = 1e5 + 5;
const int maxb = 30;
const int mod = 1e9 + 7;
struct Node {
    
    int first , second;
}a[maxn];
int bk[maxn] , u , v , tg[maxn];
inline int calc (int up , int x , int id){
    
    if ((up & x) == x) return up; //  prune 1: Prevent all 1( Or a lot 1) Of up appear 
    for (int i = maxb ; i >= 0 ; i--){
    
        u = (up >> i) & 1;
        v = (x >> i) & 1;
        if (u == v) continue;
        if ((x | (1 << i)) > up) {
     //  This situation means that this range will not be used in the future check 了 .
            tg[id] = true;
            return x | ((1 << i) - 1);
        }
        x |= (1 << i);
    }
    assert(x == up);
    return x;
}
template <typename T>
void read(T & x){
     x = 0;T f = 1;char ch = getchar();while(!isdigit(ch)){
    if(ch == '-') f = -1;
ch = getchar();}while (isdigit(ch)){
    x = x * 10 + (ch ^ 48);ch = getchar();}x *= f;}
template <typename T>
void write(T x){
    if(x < 0){
    putchar('-');x = -x;}if (x > 9)write(x / 10);putchar(x % 10 + '0');}
int main()
{
    
    int t; read(t);
    while (t--){
    
        int n ; read(n);
        for (int i = 1 ; i <= n ; i++){
    
            read(a[i].first);
            read(a[i].second);
            bk[i] = false;
        }
        int ans = 0;
        for (int i = maxb ; i >= 0 ; i--){
    
            ll tmp = ans | (1 << i);
            bool ok = true;
            for (int j = 1 ; j <= n && ok; j++){
    
                if (bk[j]) continue;
                if (tmp > a[j].second) ok = false;
                tg[j] = false;
                int mx = calc (a[j].second , tmp , j);
                if (mx < a[j].first) ok = false;
            }
            if (ok) {
    
                ans = tmp;
                for (int j = 1 ; j <= n ; j++) if (tg[j]) bk[j] = true;
            }
        }
        write(ans);
        puts("");
    }
    return 0;
}