线段树

显然的方法是把区间离散化以后，维护每个区间内出现的数的个数。

查询的时候直接用左端点的值加上查询的数的排名/区间插入的次数就行了。

处理这类问题一般是让每个端点的右区间+1，然后用叶子节点来保存一段区间的信息。

当我们的线段树递归到叶子结点的时候，l = r, 我们如果让线段树维护当前区间每个数出现的次数，叶子节点显然不好处理，因为l = r。

所以我们可以让每个区间维护的信息往后扩展一点。

假设当前区间为[l...r], 这里l和r均为离散化以后的值。此时可以让线段树维护[l..r+1)区间内每个数出现的次数，这样到了叶子节点实际上是[l, l+1)区间内每个数出现的次数,(此时l=r)。

这样问题就简化完成了。

在修改的时候也要让右端点-1，这样才符合我们对维护的信息的定义.

#include 
    
     #define INF 0x3f3f3f3f#define full(a, b) memset(a, b, sizeof a)#define __fastIn ios::sync_with_stdio(false), cin.tie(0)#define range(x) (x).begin(), (x).end()#define pb push_backusing namespace std;typedef long long LL;inline int lowbit(int x){ return x & (-x); }inline int read(){    int ret = 0, w = 0; char ch = 0;    while(!isdigit(ch)){        w |= ch == '-', ch = getchar();    }    while(isdigit(ch)){        ret = (ret << 3) + (ret << 1) + (ch ^ 48);        ch = getchar();    }    return w ? -ret : ret;}template 
     
      inline A __lcm(A a, A b){ return a / __gcd(a, b) * b; }template 
      
       inline A fpow(A x, B p, C lyd){    A ans = 1;    for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;    return ans;}const int N = 400005;int n, x[N], y[N], L[N], R[N], a1, b1, c1, a2, b2, c2, m1, m2, b[N<<1], tot;int lazy[N<<3];LL freq[N<<3]; void add(int rt, int l, int r, int val){    lazy[rt] += val;    freq[rt] += 1LL * (b[r + 1] - b[l]) * val;} void push_down(int rt, int l, int r, int val){    int mid = (l + r) >> 1;    add(rt << 1, l, mid, val);    add(rt << 1 | 1, mid + 1, r, val);    lazy[rt] = 0;} void push_up(int rt){    freq[rt] = freq[rt << 1] + freq[rt << 1 | 1];} void buildTree(int rt, int l, int r){    if(l == r){        freq[rt] = lazy[rt] = 0;        return;    }    int mid = (l + r) >> 1;    buildTree(rt << 1, l, mid);    buildTree(rt << 1 | 1, mid + 1, r);    push_up(rt);} void insert(int rt, int l, int r, int il, int ir){    if(l == il && r == ir){        add(rt, l, r, 1);        return;    }    push_down(rt, l, r, lazy[rt]);    int mid = (l + r) >> 1;    if(ir <= mid) insert(rt << 1, l, mid, il, ir);    else if(il > mid) insert(rt << 1 | 1, mid + 1, r, il, ir);    else insert(rt << 1, l, mid, il, mid), insert(rt << 1 | 1, mid + 1, r, mid + 1, ir);    push_up(rt);} int query(int rt, int l, int r, LL k){    if(l > r) return 0;    if(l == r){        return b[l] + (k - 1) / lazy[rt];    }    push_down(rt, l, r, lazy[rt]);    int mid = (l + r) >> 1;    if(freq[rt << 1] >= k) return query(rt << 1, l, mid, k);    return query(rt << 1 | 1, mid + 1, r, k - freq[rt << 1]);} int main(){     scanf("%d", &n);    scanf("%d%d%d%d%d%d", &x[1], &x[2], &a1, &b1, &c1, &m1);    scanf("%d%d%d%d%d%d", &y[1], &y[2], &a2, &b2, &c2, &m2);    for(int i = 3; i <= n; i ++){        x[i] = (1LL * a1 * x[i - 1] + 1LL * b1 * x[i - 2] + c1) % m1;        y[i] = (1LL * a2 * y[i - 1] + 1LL * b2 * y[i - 2] + c2) % m2;    }    for(int i = 1; i <= n; i ++){        L[i] = min(x[i], y[i]) + 1;        R[i] = max(x[i], y[i]) + 1;        R[i] ++, b[++tot] = L[i], b[++tot] = R[i];    }    sort(b + 1, b + tot + 1);    tot = (int)(unique(b + 1, b + tot + 1) - b - 1);//    b[tot + 1] = b[tot] + 1;//    tot ++;    LL sum = 0;    buildTree(1, 1, tot);    for(int i = 1; i <= n; i ++){        sum += R[i] - L[i];        L[i] = (int)(lower_bound(b + 1, b + tot + 1, L[i]) - b);        R[i] = (int)(lower_bound(b + 1, b + tot + 1, R[i]) - b);        insert(1, 1, tot, L[i], R[i] - 1);        printf("%d\n", query(1, 1, tot, (sum + 1) / 2));    }    return 0;}