2016″百度之星” – 复赛(Astar
Round3)

https://www.luogu.org/problemnew/show/P3960

1003 拍照

思路:先拿具有的线条在x轴上而观察到之职务要出,起点和极对应数组a里之x,y,排序后从坐标最小开枚举。如果遇到起点标志,就加同(说明从这职位上马好瞥见);结束点表明减一(说明从者岗位上马不可见)。还有一个值得注意的凡:只有向左行驶的船舶可见坐标大于向右侧行驶的轮,才可能在某个时刻以起于照里

/**************************************************************
    Problem:hdu 5417
    User: youmi
    Language: C++
    Result: Accepted
    Time:1591MS
    Memory:1816K
****************************************************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <cmath>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#define zeros(a) memset(a,0,sizeof(a))
#define ones(a) memset(a,-1,sizeof(a))
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scs(a) scanf("%s",a)
#define sclld(a) scanf("%I64d",&a)
#define pt(a) printf("%d\n",a)
#define ptlld(a) printf("%I64d\n",a)
#define rep(i,from,to) for(int i=from;i<=to;i++)
#define irep(i,to,from) for(int i=to;i>=from;i--)
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define lson (step<<1)
#define rson (lson+1)
#define eps 1e-6
#define oo 0x3fffffff
#define TEST cout<<"*************************"<<endl
const double pi=4*atan(1.0);

using namespace std;
typedef long long ll;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
const int maxn=20000+10;
int n,cnt,x,y,z,d,po,lmax,l,r,ans;
struct data
{
    int x,y,z;
}a[maxn];
bool cmp(data a,data b)
{
    if (a.x!=b.x) return a.x<b.x;
    else
    {
        if (a.y!=b.y) return a.y<b.y; else return a.z<b.z;
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    int T_T;
    scanf("%d",&T_T);
    for(int kase=1;kase<=T_T;kase++)
    {
        n=read(); cnt=0;
        for (int i=1;i<=n;i++)
        {
            x=read(),y=read(),z=read(),d=read();
            if (y-x<=2*z)
            {
                if (d==1) po=0; else po=1;
                a[++cnt].x=y-z; a[cnt].y=0; a[cnt].z=po;
                a[++cnt].x=x+z; a[cnt].y=1; a[cnt].z=po;
            }
        }
        sort(a+1,a+cnt+1,cmp);
        lmax=l=r=ans=0;
        for (int i=1;i<=cnt;i++)
        {
            if (a[i].z==0)
            {
                if (a[i].y==0) ++l; else --l;
            }
            else
            {
                if (a[i].y==0) ++r; else --r;
            }
            if (l>lmax) lmax=l;
            if (lmax+r>ans) ans=lmax+r;
        }
        printf("Case #%d:\n%d\n",kase,ans);
    }
    return 0;
}

View Code

 

2016″百度之星” – 初赛(Astar
Round2B)

1001 区间的值

思路:先选出[l,r]区间内的极小值,然后枚举[l,r]内的所为价,就可算是出以a[p]呢最小值的具有区间的【区间的价】了;不过出某些亟需专注:在以a[p]啊
       
 最小值时,计算起底【区间大小大于等于3】(假而间隔大小为k)的【区间的值】,应该是距离大小也[2,k]内的极其老价值。

/**************************************************************
    Problem:hdu 5696
    User: youmi
    Language: C++
    Result: Accepted
    Time:1419MS
    Memory:4484K
****************************************************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <cmath>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#define zeros(a) memset(a,0,sizeof(a))
#define ones(a) memset(a,-1,sizeof(a))
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scs(a) scanf("%s",a)
#define sclld(a) scanf("%I64d",&a)
#define pt(a) printf("%d\n",a)
#define ptlld(a) printf("%I64d\n",a)
#define rep(i,from,to) for(int i=from;i<=to;i++)
#define irep(i,to,from) for(int i=to;i>=from;i--)
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define lson (step<<1)
#define rson (lson+1)
#define eps 1e-6
#define oo 0x3fffffff
#define TEST cout<<"*************************"<<endl
const double pi=4*atan(1.0);

using namespace std;
typedef long long ll;
template <class T> inline void read(T &n)
{
    char c; int flag = 1;
    for (c = getchar(); !(c >= '0' && c <= '9' || c == '-'); c = getchar()); if (c == '-') flag = -1, n = 0; else n = c - '0';
    for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) n = n * 10 + c - '0'; n *= flag;
}
int Pow(int base, ll n, int mo)
{
    if (n == 0) return 1;
    if (n == 1) return base % mo;
    int tmp = Pow(base, n >> 1, mo);
    tmp = (ll)tmp * tmp % mo;
    if (n & 1) tmp = (ll)tmp * base % mo;
    return tmp;
}
//***************************

int n;
const int maxn=200000+10;
int a[maxn];
ll ans[maxn];
ll temp[maxn];
void sovle(int l,int r)
{
    if(r<l)
        return ;
    int p=0;
    int len=(r-l+1);
    rep(i,0,len)
        temp[i]=0;
    rep(i,l,r)
    {
        if(a[i]<a[p])
            p=i;
    }
    rep(i,l,p)
        temp[p-l+1]=Max(temp[p-l+1],1ll*a[p]*a[i]);
    rep(i,p,r)
        temp[r-p+1]=Max(temp[r-p+1],1ll*a[p]*a[i]);
    rep(i,3,len)
        temp[i]=Max(temp[i],temp[i-1]);
    rep(i,1,len)
        ans[i]=Max(ans[i],temp[i]);
    sovle(l,p-1);
    sovle(p+1,r);
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    while(~sc(n))
    {
        a[0]=oo;
        rep(i,1,n)
            sc(a[i]);
        zeros(ans);
        sovle(1,n);
        rep(i,1,n)
            ptlld(ans[i]);
    }
}

View Code

 1003 瞬间走

思路:C(n-2,n+m-4);

1005 区间交

思路:对区间起末坐标存入数组排序,然后枚举,遇到起点存入队列,遇到末点更新答案。下面是具体做法:

据此y数组记录下依次区间的id,l,r;并因此x数组记录下区间的id,区间从(末)坐标并记为自(末);对x数组进行排序,然后一一枚举x数组并将记为于始点的坐标压入队列,这里的阵用数组实现。当然是历程我们得简单个数组:index用来号队列中点对应之间隔id,pt用来号区间id对诺队列中的职位。如果也自始点,那么我们直接抑制入行就好了。如果为末点,我们即便得处理外。

拍卖操作:

  1. 先是,如果队列元素个数小于k,直接拿班中id对应的职位弹出来就吓了,我们这里是记为-1;
  2. 假若个数大于等于k,我们就创新答案。因为我们早已指向x排序过,所以先进行列的序幕坐标值肯定更小;而我们唯有需要k个区间交就是好了,所以我们获取队列中之第k只价值来算。这里第k个价所指向许队列中的岗位我们所以flag记录。
  3. 而手上处理的id在班中的职务于flag前面,那么flag指向的凡k-1单区间交的职,所以我们而持续朝着后查找。因为被弹有行列的位置都受标记为-1,所以while循环到非-1就是现阶段之k个区间交对应之职位。

/**************************************************************
    Problem:hdu 5700
    User: youmi
    Language: C++
    Result: Accepted
    Time:1996MS
    Memory:7208K
****************************************************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <cmath>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#define zeros(a) memset(a,0,sizeof(a))
#define ones(a) memset(a,-1,sizeof(a))
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scs(a) scanf("%s",a)
#define sclld(a) scanf("%I64d",&a)
#define pt(a) printf("%d\n",a)
#define ptlld(a) printf("%I64d\n",a)
#define rep(i,from,to) for(int i=from;i<=to;i++)
#define irep(i,to,from) for(int i=to;i>=from;i--)
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define lson (step<<1)
#define rson (lson+1)
#define eps 1e-6
#define oo 0x3fffffff
#define TEST cout<<"*************************"<<endl
const double pi=4*atan(1.0);

using namespace std;
typedef long long ll;
template <class T> inline void read(T &n)
{
    char c; int flag = 1;
    for (c = getchar(); !(c >= '0' && c <= '9' || c == '-'); c = getchar()); if (c == '-') flag = -1, n = 0; else n = c - '0';
    for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) n = n * 10 + c - '0'; n *= flag;
}
int Pow(int base, ll n, int mo)
{
    if (n == 0) return 1;
    if (n == 1) return base % mo;
    int tmp = Pow(base, n >> 1, mo);
    tmp = (ll)tmp * tmp % mo;
    if (n & 1) tmp = (ll)tmp * base % mo;
    return tmp;
}
//***************************

int n,k,m;
const int maxn=100000+10;
int a[maxn];
ll sum[maxn];
struct T
{
    int id,l,r;
    void init(int _id,int _l,int _r)
    {
        id=_id,l=_l,r=_r;
    }
}y[maxn];
struct Y
{
    int id,p,dir;
    void init(int _id,int _p,int _dir)
    {
        id=_id,p=_p,dir=_dir;
    }
}x[maxn<<1];
bool cmp(struct Y b,struct Y c)
{
    if(b.p==c.p)
        return b.dir<c.dir;
    return b.p<c.p;
}

int index[maxn];
int pt[maxn];
void sovle()
{
    ll ans=0;
    zeros(pt);
    zeros(index);
    int head=1,sz=0,flag=-1;
    rep(i,1,2*m)
    {
        if(x[i].dir==0)
        {
            index[head]=x[i].id;
            pt[x[i].id]=head;
            head++,sz++;
            if(sz==k)
                flag=head-1;
        }
        else
        {
            if(sz>=k)
            {
                ans=Max(ans,sum[x[i].p]-sum[y[index[flag]].l-1]);
                if(pt[x[i].id]<=flag&&sz-1>=k)
                {
                    flag++;
                    while(index[flag]==-1&&flag<=head)
                    {
                        flag++;
                    }
                }
            }
            sz--;
            index[pt[x[i].id]]=-1;
        }
    }
    ptlld(ans);
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    while(~sc3(n,k,m))
    {
        rep(i,1,n)
            sc(a[i]);
        sum[0]=0;
        sum[1]=a[1];
        rep(i,2,n)
            sum[i]=sum[i-1]+a[i];
        int l,r;
        rep(i,1,m)
        {
            sc2(l,r);
            x[i*2-1].init(i,l,0);
            x[i*2].init(i,r,1);
            y[i].init(i,l,r);
        }
        sort(x+1,x+1+2*m,cmp);
        sovle();
    }
}

View Code

 

1006 中各数计数

思路:这个问题可分类为01分规划里到底结果了,所以都链接到那么篇博文了

 

2016″百度之星” – 初赛(Astar
Round2A)

1001 ALL X

思路:x*(10n-1)/9,之后的相应就是概括了

1002  Sitting in Line

夫就重新博客里描写了了,所以将题目就连续到写的充分博客了

1003 snacks

思路:这个书要求一个子树里的极其要命价值。先dfs一整个整棵树,并且记录一个触及入下的id和出的id,那么这片个id之间就是这点之子树了。然后使线段树处理一下,nlogn复杂度

/**************************************************************
    Problem:hdu 5692
    User: youmi
    Language: C++
    Result: Accepted
    Time:2355MS
    Memory:14932K
****************************************************************/
#pragma comment(linker, "/STACK:1024000000,1024000000")
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <cmath>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ctime>
#define zeros(a) memset(a,0,sizeof(a))
#define ones(a) memset(a,-1,sizeof(a))
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scs(a) scanf("%s",a)
#define sclld(a) scanf("%I64d",&a)
#define pt(a) printf("%d\n",a)
#define ptlld(a) printf("%I64d\n",a)
#define rep(i,from,to) for(int i=from;i<=to;i++)
#define irep(i,to,from) for(int i=to;i>=from;i--)
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define lson (step<<1)
#define rson (lson+1)
#define eps 1e-6
#define oo 0x3fffffff
#define TEST cout<<"*************************"<<endl
const double pi=4*atan(1.0);
using namespace std;
typedef long long ll;
ll n,m;
ll z,x,y;
const int maxn=100000+10;
int in[maxn],out[maxn];
ll val[maxn];
ll dp[maxn];
int head[maxn];
int T=0,id;
struct side
{
    int v,next;
}e[maxn];
struct segment
{
    int l,r;
    ll mx,cg;
    void init(ll a,ll b,ll c,ll d)
    {
        l=a,r=b,mx=c,cg=d;
    }
}seg[maxn<<2];
inline ll read()
{
    ll x=0,f=1; char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
void init()
{
    T=0;
    id=0;
    ones(head);
}
void build(int u,int v)
{
    e[T].v=v;
    e[T].next=head[u];
    head[u]=T++;
}
void dfs(int u,int f,ll c)
{
    in[u]=++id;
    if(u==0)
        dp[id]=c;
    else
        dp[id]=dp[in[f]]+c;
    for(int i=head[u];~i;i=e[i].next)
    {
        int v=e[i].v;
        if(v!=f)
            dfs(v,u,val[v]);
    }
    out[u]=id;
}
void pushup(int step)
{
    seg[step].mx=Max(seg[lson].mx,seg[rson].mx);
}
void pushdown(int step)
{
    seg[lson].mx+=seg[step].cg;
    seg[rson].mx+=seg[step].cg;
    seg[lson].cg+=seg[step].cg;
    seg[rson].cg+=seg[step].cg;
    seg[step].cg=0;
}
void build(int step,int l,int r)
{
    seg[step].init(l,r,0,0);
    if(l==r)
    {
        seg[step].init(l,r,dp[l],0);
        return;
    }
    int mid=(l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(step);
}
void update(int step,int l,int r,ll c)
{
    if(seg[step].l==l&&seg[step].r==r)
    {
        seg[step].cg+=c;
        seg[step].mx+=c;
        return ;
    }
    pushdown(step);
    int mid=(seg[step].l+seg[step].r)>>1;
    if(l>mid)
        update(rson,l,r,c);
    else if(mid>=r)
        update(lson,l,r,c);
    else
    {
        update(lson,l,mid,c);
        update(rson,mid+1,r,c);
    }
    pushup(step);
}
ll query(int step,int l,int r)
{
    if(seg[step].l==l&&seg[step].r==r)
    {
        return seg[step].mx;
    }
    pushdown(step);
    int mid=(seg[step].l+seg[step].r)>>1;
    if(l>mid)
        return query(rson,l,r);
    else if(mid>=r)
        return query(lson,l,r);
    else
    {
        ll temp=query(lson,l,mid);
        temp=Max(temp,query(rson,mid+1,r));
        return temp;
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    int T_T;
    scanf("%d",&T_T);
    for(int kase=1;kase<=T_T;kase++)
    {
        printf("Case #%d:\n",kase);
        n=read(),m=read();
        ll u,v;
        init();
        rep(i,1,n-1)
        {
            u=read(),v=read();
            build(u,v);
            build(v,u);
        }
        rep(i,0,n-1)
        {
            u=read();
            val[i]=u;
        }
        dfs(0,-1,val[0]);
        build(1,1,n);
        rep(i,1,m)
        {
            z=read(),x=read();
            if(z==1)
                ptlld(query(1,in[x],out[x]));
            else
            {
                y=read();
                ll temp=y-val[x];
                update(1,in[x],out[x],temp);
                val[x]+=temp;
            }
        }
    }
    return 0;
}

View Code

 

1005 BD String

思路:

1—B

2—BBD

3—BBD|B|BDD

4—BBD|B|BDD|B|BBD|D|BDD

5—BBD|B|BDD|B|BBD|D|BDD|B|BBD|B|BDD|D|BBD|D|BDD

从今第五尽可观望规律:每8单吗同组,其中BBD,BDD连续重复;4的倍数达相应之假名,又是书写给规律的起,那么这有进行dfs即可;然后对小于等于8底片段,可以用一个数组预处理。

在意:(小于等8的组成部分)与(4之倍数)在位置也4底地方更计算了平等破,所以要是错过丢就同一片

/**************************************************************
    Problem:hdu 5694
    User: youmi
    Language: C++
    Result: Accepted
    Time:0MS
    Memory:1572K
****************************************************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <cmath>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#define zeros(a) memset(a,0,sizeof(a))
#define ones(a) memset(a,-1,sizeof(a))
#define sc(a) scanf("%d",&a)
#define sc2(a,b) scanf("%d%d",&a,&b)
#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define scs(a) scanf("%s",a)
#define sclld(a) scanf("%I64d",&a)
#define pt(a) printf("%d\n",a)
#define ptlld(a) printf("%I64d\n",a)
#define rep(i,from,to) for(int i=from;i<=to;i++)
#define irep(i,to,from) for(int i=to;i>=from;i--)
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define lson (step<<1)
#define rson (lson+1)
#define eps 1e-6
#define oo 0x3fffffff
#define TEST cout<<"*************************"<<endl
const double pi=4*atan(1.0);

using namespace std;
typedef long long ll;
inline ll read()
{
    ll x=0,f=1; char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int b[]={0,1,2,2,0,3,3,3,0};
ll sovle(ll tt)
{
    if(tt==0)
        return 0;
    ll ans=0;
    ans+=sovle(tt/4);
    if(tt<4)
        return b[tt];
    else if(tt<8)
    {
        if(tt==4)
            return ans+b[3];
        else
            return ans+b[tt];
    }
    ans+=3*(tt/8);
    ans+=sovle(tt%8);
    if(tt%8>=4)
        ans-=1;
    return ans;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    int T_T;
    scanf("%d",&T_T);
    for(int kase=1;kase<=T_T;kase++)
    {
        ll l,r;
        l=read(),r=read();
        ll ans=sovle(r);
        ans-=sovle(l-1);
        ptlld(ans);
    }
}

View Code

 1006 Gym Class

这贪得无厌+拓扑就好了,所以这边也直接把链接给到对应博客了

p<=500 50分 模拟

每个人之出队只会潜移默化当下施行与终极一列

p<=500,有用的实践仅来500执

故此仅保护这p行和最终一排的信

接下来模拟

光阴复杂度:O(p*(n+m))

空中复杂度:O(p*m+n)

 

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

#define N 501
#define M 50001

typedef long long LL;

LL pos[N][M],last[M];

struct node
{
    int x,y;
}e[N];

int h[N];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

int main()
{
    int n,m,q;
    read(n); read(m); read(q);
    for(int i=1;i<=q;++i) 
    {
        read(e[i].x);
        read(e[i].y);
        h[i]=e[i].x;
    }
    sort(h+1,h+q+1);
    int tot=unique(h+1,h+q+1)-h-1;
    LL t;
    for(int i=1;i<=tot;++i)
    {
        t=(LL)(h[i]-1)*m;
        for(int j=1;j<=m;++j) pos[i][j]=++t;
    }
    for(int i=1;i<=n;++i) last[i]=last[i-1]+m;
    int nx;
    LL ans;
    for(int i=1;i<=q;++i)
    {
        nx=lower_bound(h+1,h+tot+1,e[i].x)-h;
        if(e[i].y==m) ans=last[h[nx]];
        else ans=pos[nx][e[i].y];
        cout<<ans<<'\n';
        if(e[i].y!=m)
        {
            for(int j=e[i].y;j<m-1;++j) pos[nx][j]=pos[nx][j+1];
            pos[nx][m-1]=last[h[nx]];
        }
        for(int j=h[nx];j<n;++j) last[j]=last[j+1];
        last[n]=ans;
    }
}

View Code

 

x=1

x=1,全部底操作就涉及第一实践和终极一排

就此数据结构分别维护第一行A和结尾一列B

历次的出队相当给查询A中的第k只因素

接下来B中最后插入一个勤

当A备受不足k个因素时,到B中查看第k-|A|独元素

 

30分 线段树

A中以第i个数的价作为下标

B中因为第i个数被插入到B中之依次作下标,另用a数组存它的价值

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;

#define N 300001

typedef long long LL;

int n;

int sum[N<<2];

LL a[N<<1];
int sum2[N<<3];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

void build(int k,int l,int r)
{
    sum[k]=r-l+1;
    if(l==r)  return; 
    int mid=l+r>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
}

int query(int k,int l,int r,int pos)
{
    if(l==r) return l;
    int mid=l+r>>1;
    if(pos<=sum[k<<1]) return query(k<<1,l,mid,pos);
    return query(k<<1|1,mid+1,r,pos-sum[k<<1]);
}

void change(int k,int l,int r,int pos)
{
    if(l==r)
    {
        sum[k]=0;
        return;
    }
    int mid=l+r>>1;
    if(pos<=mid) change(k<<1,l,mid,pos);
    else change(k<<1|1,mid+1,r,pos);
    sum[k]=sum[k<<1]+sum[k<<1|1];
}

void build2(int k,int l,int r)
{
    if(l==r) 
    {
        if(l<=n) sum2[k]=1;
        return;
    }
    int mid=l+r>>1;
    build2(k<<1,l,mid);
    build2(k<<1|1,mid+1,r);
    sum2[k]=sum2[k<<1]+sum2[k<<1|1];
}

int query2(int k,int l,int r,int pos)
{
    if(l==r) return l;
    int mid=l+r>>1;
    if(pos<=sum2[k<<1]) return query2(k<<1,l,mid,pos);
    return query2(k<<1|1,mid+1,r,pos-sum2[k<<1]);
}

void change2(int k,int l,int r,int pos,int w)
{
    if(l==r)
    {
        sum2[k]=w;
        return;
    }
    int mid=l+r>>1;
    if(pos<=mid) change2(k<<1,l,mid,pos,w);
    else change2(k<<1|1,mid+1,r,pos,w);
    sum2[k]=sum2[k<<1]+sum2[k<<1|1];
}

int main()
{
    int m,q;
    read(n); read(m); read(q);
    build(1,1,m-1);
    int i=1; LL j=m;
    for(;i<=n;j+=m,++i) a[i]=j;
    build2(1,1,n+q);
    int x,y;  LL ans; 
    for(int i=1;i<=q;++i)
    {
        read(x); read(y);
        if(y<=sum[1])
        {
            ans=query(1,1,m-1,y);
            cout<<ans<<'\n';
            change(1,1,m-1,ans);
            change2(1,1,n+q,n+i,1);
            a[n+i]=ans;
        }
        else
        {
            y-=sum[1];
            y=query2(1,1,n+q,y);
            cout<<a[y]<<'\n';
            change2(1,1,n+q,y,0);
            change2(1,1,n+q,n+i,1);
            a[n+i]=a[y];
        }
    }
}

View Code

 

30分 树状数组

其余一样栽求解方式,下面100分割线段树方法吃斯类似

有限单树状数组,树状数组c1维护第1推行,树状数组c2一个保护最后1列

0 1
个别表示这个职位发生没来多次

诸如此类便足以采取树桩数组查询第k个数

以树状数组外次私分即可

故半个vector
记录后补偿加进树状数组中之频繁

开班树状数组是满之,即c1出第一履的所有数,c2发最终一排的所有数

(x,y)出队

如果y=m,那么到c2中找第1个元素t

若t<=n
输出m*x,c2的尾声加入t

否则
到对应之vector中寻觅第 t-n-1(下标从0开始)个出口, 

输出的价插入到c2的末梢

如果y!=m,到c1中找第y个元素t

若t<=m-1
输出t

否则到对应之vector中觅第t-m(下标从0开始)个出口

出口的价插入到c2的末段

 

 

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>

#define N 300001

using namespace std;

typedef long long LL;

#define lowbit(x) x&-x

int n,m,q,mx;

int c1[N<<1],c2[N<<1];
int siz_c1,siz_c2;

vector<LL>V[2];

int l,r,mid,tmp;

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

void add(int *c,int x,int w)
{
    while(x<=mx)
    {
        c[x]+=w;
        x+=lowbit(x);
    }
}

int ask(int *c,int x)
{
    int sum=0;
    while(x)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}

LL work2(int x,LL y)
{
    l=1; r=mx;
    while(l<=r)
    {
        mid=l+r>>1;
        if(ask(c2,mid)>=x) tmp=mid,r=mid-1;
        else l=mid+1;
    }
    add(c2,tmp,-1);
    LL ans=tmp<=n ? (LL)tmp*m : V[1][tmp-n-1];
    add(c2,++siz_c2,1);
    V[1].push_back(y ? y : ans);
    return ans;
}

LL work1(int x,int y)
{
    l=1; r=mx;
    while(l<=r)
    {
        mid=l+r>>1;
        if(ask(c1,mid)>=y) tmp=mid,r=mid-1;
        else l=mid+1;
    }
    add(c1,tmp,-1);
    LL ans=tmp<m ? tmp : V[0][tmp-m];
    add(c1,++siz_c1,1);
    V[0].push_back(work2(x,ans));
    return ans;
}

int main()
{
    read(n); read(m); read(q);
    mx=max(m,n)+q;
    for(int i=1;i<m;++i) add(c1,i,1);
    for(int i=1;i<=n;++i) add(c2,i,1);
    siz_c1=m-1; siz_c2=n;
    int x,y; 
    for(int i=1;i<=q;++i)
    {
        read(x); read(y);
        if(y==m) cout<<work2(x,0)<<'\n';
        else cout<<work1(x,y)<<'\n';
    }
}

View Code

 

 

30分 splay

首先履行splay0,最后一排splay1

裸地splay删除、查询k值、添加 

查询(x,y)

倘若y==m,splay1中找到第1个,输出,删除,加到最后当

否则,splay0中找到第y个,输出,从splay0中去除,加至splay1中;找到splay1中第1独,删除,加至splay0中

 

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 300001

typedef long long LL;

LL a[N];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c))  { x=x*10+c-'0'; c=getchar(); }    
}

struct SPLAY
{
    int root,tot;
    int fa[N<<1],ch[N<<1][2];
    int siz[N<<1];
    LL num[N<<1];

    void build(int l,int r,int f,LL *a)
    {
        if(l>r) return;
        int mid=l+r>>1;
        fa[mid]=f;
        ch[f][mid>f]=mid;
        num[mid]=a[mid];
        siz[mid]=1;
        build(l,mid-1,mid,a);
        build(mid+1,r,mid,a);
        siz[mid]=siz[ch[mid][0]]+siz[ch[mid][1]]+1;
    }

    void update(int x)
    {
        siz[x]=1;
        if(ch[x][0]) siz[x]+=siz[ch[x][0]];
        if(ch[x][1]) siz[x]+=siz[ch[x][1]];
    }

    bool getson(int x)
    {
        return ch[fa[x]][1]==x;
    }

    void rotate(int x)
    {
        int y=fa[x],z=fa[y],k=getson(x);
        if(y!=root) ch[z][ch[z][1]==y]=x;
        ch[y][k]=ch[x][k^1]; ch[x][k^1]=y;
        fa[x]=z; fa[y]=x; fa[ch[y][k]]=y;
        update(y);
    }

    void splay(int x)
    {
        for(int f;f=fa[x];rotate(x))
            if(fa[f]) rotate(getson(x)==getson(f) ? f : x);
        update(x);
        root=x;
    }

    void insert_last(LL x)
    {
        if(!root)
        {
            root=++tot;
            num[tot]=x;
            siz[tot]=1;
            return;
        }
        int now=root;
        while(ch[now][1]) now=ch[now][1];
        ch[now][1]=++tot;
        fa[tot]=now;
        num[tot]=x;
        siz[tot]=1;
        splay(tot);
    }

    int find_kth(int x)
    {
        int now=root;
        while(1)
        {
            if(siz[ch[now][0]]+1==x) return now;
            if(ch[now][0] && siz[ch[now][0]]>=x)
            {
                now=ch[now][0];
                continue;
            }
            x-=siz[ch[now][0]]+1;
            now=ch[now][1];
        }
    }

    int getpre()
    {
        int now=ch[root][0];
        while(ch[now][1]) now=ch[now][1];
        return now;
    }

    void del()
    {
        if(!ch[root][0] && !ch[root][1])
        {
            root=0;
            return;
        }
        if(!ch[root][0])
        {
            root=ch[root][1];
            fa[root]=0;
            return;
        }
        if(!ch[root][1])
        {
            root=ch[root][0];
            fa[root]=0;
            return;
        }
        int pre=getpre();
        int tmp=root;
        splay(pre);
        ch[root][1]=ch[tmp][1];
        fa[ch[root][1]]=root;
        update(root);
    }

}Splay[2];

int main()
{
    int n,m,q;
    read(n); 
    read(m); 
    read(q);
    int i; LL j;
    for(i=1;i<m;++i)  
        a[i]=i;
    Splay[0].build(1,m-1,0,a);
    Splay[0].tot=m-1;
    Splay[0].root=m>>1;
    for(i=1,j=m;i<=n;++i,j+=m) 
        a[i]=j;
    Splay[1].build(1,n,0,a);
    Splay[1].tot=n;
    Splay[1].root=n+1>>1; 
    int x,y; int id0,id1;
    for(i=1;i<=q;++i)
    {
        read(x);
        read(y);
        if(y==m)
        {
            id0=Splay[1].find_kth(1);
            Splay[1].splay(id0);
            Splay[1].del();
            Splay[1].insert_last(Splay[0].num[id0]);
            cout<<Splay[1].num[id0];
            continue;
        }
        id0=Splay[0].find_kth(y);
        Splay[0].splay(id0);
        Splay[0].del();
        Splay[1].insert_last(Splay[0].num[id0]);
        id1=Splay[1].find_kth(x);
        Splay[1].splay(id1);
        Splay[1].del();
        Splay[0].insert_last(Splay[1].num[id1]);
        cout<<Splay[0].num[id0]<<'\n';
    }    
}

View Code

 

 

满分做法

 

同x=1的做法类似

咱仅需要因此n个数据结构Ai维护每一行的前m-1单

复就此一个数据结构B维护最后一排列即可

留神所挑选数据结构的上空问题

诸一样潮查询(x,y)

如果y不是最后一排,就打Ax中找到第y独因素,记为ans,输出ans,Ax中删去ans,

将B中之第x独因素插到Ax的终极对,把ans插到B的末尾给

要是y是最终一排,在B中找到第y个因素,记为ans,输出ans,B中删去ans

将ans插入到B的终极一个

 

100分 线段树

 

对此各一样履行维护一个丝段树

妇孺皆知不能够超前都开始满,所以动态开节点 

 

丝段树区间维护的轻重缓急固定,所以动态删除和动态增长非是坏有益

所以未直接执行删除操作,不在线段子树上添加

起来我们默认维护前n行m-1排列的线树中所有节点都是满载的

保安最后一排列的线树为是满载之

 

删去操作:

用sum[k]记录下k包含的即刻段距离删除的多次之个数

如此这般查询时,当前距离数之个数
为区间大小-sum[k]

设要查的数<=区间大小-sum[k]
到不当孩子翻

不然,查的往往减去 区中大小-sum[k]
,到右手孩子翻

 

丰富操作:

使开n+1个vector,存储动态增长到对承诺线段树里的反复

 

查询操作:

如果y=m,

倘若维护最后一列的线条树是第n+1粒

询问第n+1发线段树里第x单值pos

若pos<=n,输出 pos*m,

要不输出第n+1独vector里第pos-n-1(下标从0开始)个因素

输出的价插入到最后一排列的线段树的尾声

如果y!=m

至第x发线段树里查询第y个数pos

若pos<=m-1,输出(x-1)*m+pos,

要不然输出第x独vector里
第pos-m(下标从0开始)个元素

输出的价插入到最终一列线段树的尾声

 

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;

#define N 300001

typedef long long LL;

int n,m,q,mx;

int tot;
int root[N+1],lc[N*20],rc[N*20];
int sum[N*20];

int pos;

vector<LL>V[N];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

int query(int k,int l,int r,int w)
{
    if(l==r) return l;
    int mid=l+r>>1,tmp=mid-l+1-sum[lc[k]];
    if(w<=tmp) return query(lc[k],l,mid,w);
    return query(rc[k],mid+1,r,w-tmp);
}

void change(int &k,int l,int r)
{
    if(!k) k=++tot;
    sum[k]++;
    if(l==r) return;
    int mid=l+r>>1;
    if(pos<=mid) change(lc[k],l,mid);
    else change(rc[k],mid+1,r);
}

LL work0(int x,LL y)
{
    pos=query(root[n+1],1,mx,x);
    change(root[n+1],1,mx);
    LL ans=pos<=n ? (LL)pos*m : V[n+1][pos-n-1];
    V[n+1].push_back(y ? y : ans);
    return ans;
}

LL work1(int x,int y)
{
    pos=query(root[x],1,mx,y);
    change(root[x],1,mx);
    LL ans=pos<m ? (LL)(x-1)*m+pos : V[x][pos-m];
    V[x].push_back(work0(x,ans));
    return ans;
}

int main()
{
    read(n); read(m); read(q);
    mx=max(n,m)+q;
    int x,y;
    while(q--)
    {
        read(x); read(y);
        if(y==m) cout<<work0(x,0)<<'\n';
        else cout<<work1(x,y)<<'\n';
    }
}

View Code

 

100分 树状数组

树状数组不能够动态开节点

30分树状数组做法受到,树状数组的意图是查询k值

每当此我们仍单纯所以树状数组查询k值

 

咱们不存储没有离队了之素,因为懂得了它同样开始于第i实践第j排列后就是足以汲取它的号是(i-1)*m+j

若会离队之要素至多单单发生q个

从而对于各一行的前m-1列和尾声一列都从头一个vector
Ai,B,记录本行或最后一排上进的号

 

历次询问的(x,y)是第j单冒出在第x推行之勤独与
这次询问前对第x执行开展的刺探关于

默认原来队列中的多次是第1届m个出现于同行业的累累

这就是说便可读入所有数据,离线处理

倘我们会处理发生各个一个询问(x,y)应该是第几独冒出于第x实践之高频,记否pre[i]

接下来照输入顺序枚举每一个询问(x,y)

若y!=m,2个操作:

1、第x行第pre[i]个数出队,到结尾一列的最终一个职,即vector
B中参加第x执行第pre[i]个数

2、第x实施最终加及最终一排的第x个数,即vector Ax
中在 最后一排列的第x个数

若y==m,

说到底一列的第x个数出队,到终极一排末尾,vector
B中在最后一列第x个数

 

何以得到
最后一排的第x个数?

树状数组维护最后一排,每查询同一次(x,y),标记一次x

对树状数组中查及的第x独数h,意为是第h单冒出在终极一列的频繁

若h<=n,则为h*m

若h>m,那就是vector B
中第h-n-1(下标从0开始)个元素

 

何以取得第x履第pre[i]个冒出的数?

若pre[i]<m,就是(x-1)*m+pre[i]

若pre[i]>=m,就是vector Ax 中
第pre[i]-m(下标从0开始)个冒出的往往

 

什么样收获第i个询问(x,y)的pre[i]?

枚举每一样执行,

每当树状数组中第二细分有第y个数在谁位置

处理一个,树状数组中删一个

处理了一行之后,再管前面去的还加回来供下一行以

诸如此类我们即便取得了各个一个询问(x,y)应该是第几个冒出于第x执的累累

 

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>

using namespace std;

#define N 300001

typedef long long LL;

#define lowbit(x) x&-x

int mx;
int n,m,q;

struct node
{
    int pos,id;

    node(int pos_=0,int id_=0) : pos(pos_),id(id_)  { }

};
vector<node>V[N];
vector<LL>num[N];

int c[N<<1];

int qx[N],qy[N];

int pre[N];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c))  { x=x*10+c-'0'; c=getchar(); }
}

void add(int x,int w)
{
    while(x<=mx)
    {
        c[x]+=w;
        x+=lowbit(x);
    }
}

int ask(int x)
{
    int sum=0;
    while(x)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}

int query_kth(int k) 
{  
    int l=0,r=mx;
    int mid,tmp;
    while(l<=r)
    {
        mid=l+r>>1;
        if(ask(mid)>=k) tmp=mid,r=mid-1;
        else l=mid+1;
    }
    return tmp;
}

void init()
{
    read(n); read(m); read(q);
    mx=max(n,m)+q;
    for(int i=1;i<=q;++i)
    {
        read(qx[i]); read(qy[i]);
        if(qy[i]!=m) V[qx[i]].push_back(node(qy[i],i));
    }
}

void solve1()
{
    for(int i=1;i<=mx;++i) add(i,1);
    int siz;
    node now;
    for(int i=1;i<=n;++i)
    {
        siz=V[i].size();
        for(int j=0;j<siz;++j)
        {
            now=V[i][j];
            pre[now.id]=query_kth(now.pos);
            add(pre[now.id],-1);
        }
        for(int j=0;j<siz;++j) add(pre[V[i][j].id],1);
    }
}

void solve2()
{
    LL ans; int h;
    for(int i=1;i<=q;++i)
    {
        h=query_kth(qx[i]);
        ans= h<=n ? (LL)h*m : num[0][h-n-1];
        add(h,-1);
        if(qy[i]!=m)
        {
            num[qx[i]].push_back(ans);
            ans= pre[i]<m ? LL(qx[i]-1)*m+pre[i] : num[qx[i]][pre[i]-m];
        }
        num[0].push_back(ans);
        cout<<ans<<'\n';
    }
}

int main()
{
    init();
    solve1();
    solve2();
}

View Code

 

100分 splay

 没有运用的间隔都减少成一个异常节点

各个一样履行一个splay,最后一排列一个splay

无独有偶起每一行的前m-1列都缩减成一个沾

终极一列的splay把元素填进

同30分殊的是询问的时节需要分裂节点

 

 

#include<cstdio>
#include<iostream>

using namespace std;

#define N 300001

typedef long long LL;

int tot;

int root[N];
int l[N*6],r[N*6];

int ch[N*6][2],fa[N*6],siz[N*6],key[N*6];
LL num[N*6];

int rt;

LL a[N];

void read(int &x)
{
    x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

void build(int l,int r,int f)
{
    if(l>r) return;
    int mid=l+r>>1;
    fa[mid]=f;
    ch[f][mid>f]=mid;
    key[mid]=siz[mid]=1;
    num[mid]=a[mid];
    build(l,mid-1,mid);
    build(mid+1,r,mid);
    siz[mid]=siz[ch[mid][0]]+siz[ch[mid][1]]+1;
}

bool getson(int x)
{
    return ch[fa[x]][1]==x;
}

void update(int x)
{
    siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+key[x];
}

void rotate(int x,int &goal)
{
    int y=fa[x],z=fa[y]; 
    bool k=getson(x);
    if(y!=goal) ch[z][ch[z][1]==y]=x;
    else goal=x;
    ch[y][k]=ch[x][k^1];
    ch[x][k^1]=y;
    fa[x]=z; fa[y]=x; fa[ch[y][k]]=y;
    update(y);
}

void splay(int x,int &goal)
{
    int y;
    while(x!=goal)
    {
        y=fa[x];
        if(y!=goal) rotate(getson(x)==getson(y) ? y : x,goal);
        rotate(x,goal);
    }
    update(x);
}

void split(int now,int k,int id)
{
    if(k<=siz[ch[now][0]]) split(ch[now][0],k,id);
    else if(k>siz[ch[now][0]]+key[now]) split(ch[now][1],k-siz[ch[now][0]]-key[now],id);
    else
    {
        k-=siz[ch[now][0]];
        if(k!=1)
        {
            fa[ch[++tot][0]=ch[now][0]]=tot;  
            fa[ch[now][0]=tot]=now;
            key[tot]=k-1; 
            key[now]-=k-1;
            l[tot]=l[now]; 
            r[tot]=l[now]+key[tot]-1;
            l[now]=r[tot]+1;
            update(tot);
        }
        if(key[now]!=1)
        {
            fa[ch[++tot][1]=ch[now][1]]=tot;
            fa[ch[now][1]=tot]=now;
            key[tot]=key[now]-1;
            key[now]=1;
            l[tot]=l[now]+1;
            r[tot]=r[now];
            r[now]=l[now];
            update(tot);
        }
        splay(now,root[id]);
    }
}

void insert_last(int &rt,LL x)
{
    if(!rt)
    {
        rt=++tot;
        l[tot]=r[tot]=key[tot]=siz[tot]=1;
        num[tot]=x;
        return;
    }
    int now=rt;
    while(ch[now][1]) now=ch[now][1];
    fa[++tot]=now;
    ch[now][1]=tot;
    l[tot]=r[tot]=key[tot]=siz[tot]=1;
    num[tot]=x;
    splay(tot,rt);
}

int find_kth(int now,int x)
{
    while(1)
    {
        if(x<=siz[ch[now][0]])
        {
            now=ch[now][0];
            continue;
        }
        x-=siz[ch[now][0]];
        if(x==1) return now;
        x--;
        now=ch[now][1];
    }
}

int find_pre(int rt)
{
    int now=ch[rt][0];
    while(ch[now][1]) now=ch[now][1];
    return now;
}

void del(int &rt)
{
    if(!ch[rt][0] && !ch[rt][1])
    {
        rt=0;
        return;
    }
    if(!ch[rt][0])
    {
        rt=ch[rt][1];
        return;
    }
    if(!ch[rt][1])
    {
        rt=ch[rt][0];
        return;
    }
    int pre=find_pre(rt);
    int tmp=rt;
    splay(pre,rt);
    ch[rt][1]=ch[tmp][1];
    fa[ch[rt][1]]=rt;
    update(rt);
}

int main()
{
    int n,m,q;
    read(n); read(m); read(q);
    int i; LL j;
    for(i=1,j=m;i<=n;++i,j+=m) a[i]=j;
    build(1,n,0);
    tot=n;
    root[0]=n+1>>1;
    for(int i=1;i<=n;++i)
    {
        root[i]=++tot;
        siz[tot]=m-1;
        key[tot]=m-1;
        l[tot]=1; r[tot]=m-1;
    }
    int x,y; 
    LL ans;
    int tmp;
    while(q--)
    {
        read(x); read(y);
        tmp=find_kth(root[0],x);
        splay(tmp,root[0]);
        del(root[0]);
        if(y!=m)
        {
              split(root[x],y,x);
            ans=num[root[x]] ? num[root[x]] : (LL)(x-1)*m+l[root[x]];
            del(root[x]);
            insert_last(root[0],ans);
            insert_last(root[x],num[tmp]);
        }
        else
        {
            ans=num[tmp];
            insert_last(root[0],ans);
        }
        cout<<ans<<'\n';
    }
}

View Code

 

相关文章