1.$鸽巢原理$

$即出现\%n的相关操作,那么经过n轮之后要么0-n-1的每一个数都出现一次,要么就是会出现循环$

$来源：牛客$

给定一个长度为为m的序列a,分别为$a_{0}$....$a_{m-1}$,初始值为x,第i次操作会是的x=(x+$a_{(i-1)\%m}$)%n,最少操作多少次

$解决思路：首先就是发现性质,如果是无解的话一定是陷入了一个循环,依据鸽巢原理,我们操作n次就一定会出现0-n-1或者出现
循环节,所以我们可以考虑把一次操作中的每一个值第一次出现的数的下标记录下来，然后每一轮+最后一个数即可！$

unordered_map<int,int> mp;
int t,n,m,x;
int pre[N];
void solve()
{
    cin>>n>>m>>x;
    vector<int> a(n);
    if(!x){
        cout<<0<<endl;
        return ;
    }
    for(int i=1;i<=m;i++){
        int x; cin>>x;
        pre[i]=(pre[i-1]+x)%n;
        if(!mp.count(pre[i]))  mp[pre[i]]=i;//找到每一个状态第一次出现的位置
    }

    for(int i=1;i<=n;i++){
        int ans=n-x;
        if(mp.count(ans)){
            cout<<(i-1)*m+mp[ans]<<endl;
            return ;
        }
        x=(x+pre[m])%n;
    }
    cout<<-1<<endl;

    return ;
}

2$离线树状数组$

$即出现关于区间的关系然后具有传递性质,我们可以考虑离线的树状数组$
$来源：牛客$
给定一个序列，有多次询问，每次查询区间里小于等于某个数的元素的个数给定一个序列，
即对于询问 (l,r,x)，你需要输出\$\sum_{i={l}}^{r}$$[a_{i}$<=x]值

解决思路：考虑到对于查询的数对他的影响只有在区间内比他小的数,所以我们可以按照从小到大的顺序来处理询问,依次把比当前数值小的加入到树状数中来，这样就可以实现后面查询的时候只在一定的区间内查找比自己少的数的数量即可

$也就是离线树状数组常用的写法$

int tr[N],ans[N];
PII a[N];
struct code{
    int l,r,x,id;
    bool operator<(const code&t)const{
        return x<t.x;
    }
}query[N];

void add(int x,int k){
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=k;
}

int check(int x){
    int sum=0;
    for(int i=x;i;i-=lowbit(i)) sum+=tr[i];
    return sum;
}

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x; cin>>x;
        a[i]={x,i};
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=m;i++){
        int l,r,x; cin>>l>>r>>x;
        query[i]={l,r,x,i};
    }
    sort(query+1,query+1+m);// 这样对于我们有影响的就可以放在后面来使用了，这就是
    // 树状数组的巧妙之处,多半是使用了离线的处理方式

    int left=1;
    for(int i=1;i<=m;i++){
        auto [l,r,x,id]=query[i];
        while(left<=n and a[left].first<=x){
            add(a[left].second,1);
            left++;
        }
        ans[id]=check(r)-check(l-1);
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<endl;

    return ;
}

$PS:对于区间对一个值的大小的关系查找可以容易想到主席树$

struct code{
    int l,r,cnt;
}tr[21*N];

int t,n,m;
int a[N],Smax;
int root[N],idx;

void insert(int l,int r,int last,int &now,int x){
    tr[++idx]=tr[last];
    now=idx;
    tr[now].cnt++;
    if(l==r) return ;
    int mid=l+r>>1;
    if(x<=mid) insert(l,mid,tr[last].l,tr[now].l,x);
    else insert(mid+1,r,tr[last].r,tr[now].r,x);
}

int query(int l,int r,int last,int now,int lx,int rx){
    if(r<=rx) return tr[now].cnt-tr[last].cnt;
    int mid=l+r>>1;
    if(rx<=mid) return query(l,mid,tr[last].l,tr[now].l,lx,rx);
    else if(lx>mid) return query(mid+1,r,tr[last].r,tr[now].r,lx,rx);
    else return query(l,mid,tr[last].l,tr[now].l,lx,mid)+
                query(mid+1,r,tr[last].r,tr[now].r,mid+1,rx);
}
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        Smax=max(Smax,a[i]);
    }

    for(int i=1;i<=n;i++){
       insert(1,Smax,root[i-1],root[i],a[i]);
    }

    while(m--){
        int l,r,x; cin>>l>>r>>x;
        cout<<query(1,Smax,root[l-1],root[r],1,x)<<endl;
    }

    return ;
}