C46【模板】权值线段树+离散化 P1908 逆序对

#include <bits/stdc++.h>
using namespace std;
template<typename T>void qr(T& x)
{
    x=0;int f=1;char c=getchar();
    for( ;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for( ; isdigit(c);c=getchar())x=x*10+c-48;
    x=x*f;
}
#define lc(p) (p << 1)
#define rc(p) (p << 1 | 1)
#define mid ((l + r) >> 1)
const int N=7e5+10;
struct node{int ls,rs,s;}tr[N*4];
void bt(int p, int l, int r)
{
    if(l==r){tr[p].s=1;return;}
    bt(lc(p),l,    mid);
    bt(rc(p),mid+1,  r);
    tr[p].s=tr[lc(p)].s+tr[rc(p)].s;
}
int query(int p, int l, int r, int k)
{
    tr[p].s--;
    if (l == r)return l;
    if (k <= tr[lc(p)].s) return query(lc(p), l, mid, k);
    else              return query(rc(p), mid + 1, r, k - tr[lc(p)].s);
}
int main()
{
    int n;qr(n);
    bt(1, 1, n);
    for (int i = n,x, y=0; i >= 1; --i)
    {
        qr(x);
        y=(y+x) % i;
        printf("%d\n", query(1, 1, n, y + 1));
    }
    return 0;
}

C46【模板】权值线段树+离散化 P1908 逆序对

#include <bits/stdc++.h>
using namespace std;
template<typename T>void qr(T& x)
{
x=0;int f=1;char c=getchar();
for( ;!isdigit(c);c=getchar())if(c=='-')f=-1;
for( ; isdigit(c);c=getchar())x=x10+c-48;
x=xf;
}
#define lc(p) (p << 1)
#define rc(p) (p << 1 | 1)
#define mid ((l + r) >> 1)
const int N=7e5+10;
struct node{int ls,rs,s;}tr[N*4];
void bt(int p, int l, int r)
{
if(l==r){tr[p].s=1;return;}
bt(lc(p),l,    mid);
bt(rc(p),mid+1,  r);
tr[p].s=tr[lc(p)].s+tr[rc(p)].s;
}
int query(int p, int l, int r, int k)
{
tr[p].s--;
if (l == r)return l;
if (k <= tr[lc(p)].s) return query(lc(p), l, mid, k);
else              return query(rc(p), mid + 1, r, k - tr[lc(p)].s);
}
int main()
{
int n;qr(n);
bt(1, 1, n);
for (int i = n,x, y=0; i >= 1; --i)
{
qr(x);
y=(y+x) % i;
printf("%d\n", query(1, 1, n, y + 1));
}
return 0;
}