• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

Codeforces323CTwopermutations

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

题目描述

You are given two permutations pp and qq , consisting of nn elements, and mm queries of the form: l_{1},r_{1},l_{2},r_{2}l1,r1,l2,r2 $ (l_{1}<=r_{1}; l_{2}<=r_{2}) $ . The response for the query is the number of such integers from 11 to nn , that their position in the first permutation is in segment [l_{1},r_{1}][l1,r1] (borders included), and position in the second permutation is in segment [l_{2},r_{2}][l2,r2](borders included too).

A permutation of nn elements is the sequence of nn distinct integers, each not less than 11 and not greater than nn .

Position of number v(1<=v<=n)(1<=v<=n) in permutation g_{1},g_{2},...,g_{n}g1,g2,...,gn is such number ii , that g_{i}=vgi=v .

输入输出格式

输入格式:

 

The first line contains one integer n\ (1<=n<=10^{6})n (1<=n<=106) , the number of elements in both permutations. The following line contains nn integers, separated with spaces: p_{1},p_{2},...,p_{n}\ (1<=p_{i}<=n)p1,p2,...,pn (1<=pi<=n) . These are elements of the first permutation. The next line contains the second permutation q_{1},q_{2},...,q_{n}q1,q2,...,qn in same format.

The following line contains an integer m\ (1<=m<=2·10^{5})m (1<=m<=2105) , that is the number of queries.

The following mm lines contain descriptions of queries one in a line. The description of the ii -th query consists of four integers: a,b,c,d\ (1<=a,b,c,d<=n)a,b,c,d (1<=a,b,c,d<=n) . Query parameters l_{1},r_{1},l_{2},r_{2}l1,r1,l2,r2 are obtained from the numbers a,b,c,da,b,c,dusing the following algorithm:

  1. Introduce variable xx . If it is the first query, then the variable equals 00 , else it equals the response for the previous query plus one.
  2. Introduce function f(z)=((z-1+x)\ mod\ n)+1f(z)=((z1+x) mod n)+1 .
  3. Suppose l_{1}=min(f(a),f(b)),r_{1}=max(f(a),f(b)),l_{2}=min(f(c),f(d)),r_{2}=max(f(c),f(d))l1=min(f(a),f(b)),r1=max(f(a),f(b)),l2=min(f(c),f(d)),r2=max(f(c),f(d)) .

 

输出格式:

 

Print a response for each query in a separate line.

 

输入输出样例

输入样例#1: 
3
3 1 2
3 2 1
1
1 2 3 3
输出样例#1: 
1
输入样例#2: 
4
4 3 2 1
2 3 4 1
3
1 2 3 4
1 3 2 1
1 4 2 3
输出样例#2: 
1
1
2

把第二个排列的数在第一个排列中对应的位置记一下, ** 树跑一跑就行了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#define ll long long
#define maxn 1000005
using namespace std;
struct node{
    node *lc,*rc;
    int s;
}nil[maxn*30],*rot[maxn],*cnt;
int a[maxn],n,ky,num[maxn];
int m,le,ri,k,preans=-1,ple,pri;
char ch;

inline int add(int x,int y,const int ha){
  return (x+y)%ha;
}

node *update(node *u,int l,int r){
    node *ret=++cnt;
    *ret=*u;
    ret->s++;
    
    if(l==r) return ret;
    
    int mid=l+r>>1;
    if(le<=mid) ret->lc=update(ret->lc,l,mid);
    else ret->rc=update(ret->rc,mid+1,r);
    
    return ret;
}

int query(node *u,node *v,int l,int r){
    if(l>=le&&r<=ri) return v->s-u->s;
    
    int mid=l+r>>1,an=0;
    if(le<=mid) an+=query(u->lc,v->lc,l,mid);
    if(ri>mid) an+=query(u->rc,v->rc,mid+1,r);
    return an;
}

inline void prework(){
    cnt=rot[0]=nil->lc=nil->rc=nil;
    nil->s=0;
    
    for(int i=1;i<=n;i++){
        le=a[i];
        rot[i]=update(rot[i-1],1,n);
    }
}

inline void solve(){
    scanf("%d",&m);
    while(m--){
        scanf("%d%d%d%d",&le,&ri,&ple,&pri);
        
        le=add(le,preans,n)+1;
        ri=add(ri,preans,n)+1;
        ple=add(ple,preans,n)+1;
        pri=add(pri,preans,n)+1;
        if(le>ri) swap(le,ri);
        if(ple>pri) swap(ple,pri);
                
        preans=query(rot[ple-1],rot[pri],1,n);
        printf("%d\n",preans);
    }
}

int main(){
    scanf("%d",&n);
    int now;
    for(int i=1;i<=n;i++){
        scanf("%d",&now);
        num[now]=i;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&now);
        a[i]=num[now];
    }
    
    prework();
    solve();
    
    return 0;
}

  



鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
.net/c#连接sqlserver发布时间:2022-07-14
下一篇:
C++实现邻接表发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap