Line up as NOIP2017 The last question , It's not hard , Just relative to other topics , It's a little bit of an industry

First , I use splay Maintenance of , If you don't splay, I want to learn again splay, You can come here Learn one , Now let's get down to business

First of all, the problem is the same as in previous years , Special data will give you great inspiration , In the exam , notice x=1, When there is only one line of data , I just thought of , Can maintain a balance number , Only query (x,y) because x=1, So just query the number one in the queue y Big enough , Well, think again , Maintain one for each row and last column splay that will do

But this space doesn't allow n*m A little bit , We found that , Most of the points are continuous from beginning to end , therefore , For each of these points , We can make it represent a row of continuous points , When the point to be queried is in a continuous interval , Let's take this point apart , Split into three sections ,( The original point can be retained , Modify the information , Just one more dot )

So we just need to be in the normal splay Add one more. spilt Let's split it up

inline ll split(int now,ll k)// To split, number it as now The point of , Among them the first k One is the number we want 
{
splay(now,root);
k=k+lef[now]-1;// To calculate the k The numerical
int temp=newnode(k+1,rig[now]);// Apply for a new point , Interval is k+1 to rig[now]
rig[now]=k-1;// The right end of the old interval is changed to k-1
if(!ch[now][1])// If you don't have a right son, connect
{
ch[now][1]=temp;
fa[temp]=now;
}
else// Or put the original root My right son received the new point {
int pos=nex(now);
ch[pos][0]=temp;fa[temp]=pos;
splay(temp,root);
}
return k;
}

Here is the complete code , Most operations and splay equally , No explanation

#include<bit/stdc++.h>
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i=(sign)a;i<=(sign)b;++i)
#define Fordown(i,a,b) for(register sign i=(sign)a;i>=(sign)b;--i)
const int N=3e6+5;
bool cmax(sign &a,sign b){return (a<b)?a=b,1:0;}
bool cmin(sign &a,sign b){return (a>b)?a=b,1:0;}
template<typename T>T read()
{
T ans=0,f=1;
char ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
return ans*f;
}
void file()
{
#ifndef ONLINE_JUDGE
freopen("splay.in","r",stdin);
freopen("splay.out","w",stdout);
#endif
}
int fa[N],ch[N][2],sz;
ll lef[N],rig[N],size[N];
struct splay_tree
{
int root;
inline void clear(int x){fa[x]=ch[x][0]=ch[x][1]=size[x]=lef[x]=rig[x]=0;}
inline int get(int x){return x==ch[fa[x]][1];}
inline void push_up(int x){size[x]=size[ch[x][0]]+size[ch[x][1]]+rig[x]-lef[x]+1;}
inline void rotate(int x,int &k)
{
int old=fa[x],oldfa=fa[old],o=get(x);
if(old==k)k=x;
else ch[oldfa][old==ch[oldfa][1]]=x;
fa[x]=oldfa;fa[old]=x;fa[ch[x][o^1]]=old;
ch[old][o]=ch[x][o^1];ch[x][o^1]=old;
push_up(old);push_up(x);
}
inline void splay(int x,int &k)
{
while(x^k)
{
if(fa[x]^k)rotate(get(x)^get(fa[x])?x:fa[x],k);
rotate(x,k);
}
push_up(x);
}
inline int find_last()// Because at the back , So go straight to your right son
{
int now=root;
while(ch[now][1])now=ch[now][1];
return now;
}
inline int newnode(ll l,ll r)
{
++sz;lef[sz]=l;rig[sz]=r;size[sz]=r-l+1;
return sz;
}
inline void init(ll l,ll r){root=newnode(l,r);}
inline void insert(ll v)
{
int now=newnode(v,v);
int pos=find_last();
ch[pos][1]=now;fa[now]=pos;
splay(now,root);
}
inline int pre(int x)
{
int now=ch[x][0];
while(ch[now][1])now=ch[now][1];
return now;
}
inline int nex(int x)
{
int now=ch[x][1];
while(ch[now][0])now=ch[now][0];
return now;
}
inline ll split(int now,ll k)
{
splay(now,root);
k=k+lef[now]-1;
int temp=newnode(k+1,rig[now]);
rig[now]=k-1;
if(!ch[now][1])
{
ch[now][1]=temp;
fa[temp]=now;
}
else
{
int pos=nex(now);
ch[pos][0]=temp;fa[temp]=pos;
splay(temp,root);
}
return k;
}
inline ll find_ans(ll x)// Find the first k Big
{
int now=root;ll len;
while(1)
{
if(x<=size[ch[now][0]])now=ch[now][0];
else
{
x-=size[ch[now][0]];
len=rig[now]-lef[now]+1;
if(x<=len)// The point to be found is in the interval of this point
{
//ps: If the left interval of this point is equal to the right interval , There's no need to delete it ( Very slowly ), Put the left end point ++, So the length of this point becomes 0 了 , It doesn't affect this tree
if(x==1)
{
ll res=lef[now];
lef[now]++;
splay(now,root);
push_up(now);
return res;
}
if(x==len)
{
ll res=rig[now];
rig[now]--;
splay(now,root);
push_up(now);
return res;
}
else return split(now,x);
}
x=x-(rig[now]-lef[now]+1);
now=ch[now][1];
}
}
}
}s[N];
ll n,m,q;
inline void input(){n=read<ll>();m=read<ll>();q=read<ll>();}
inline void init()
{
For(i,1,n)s[i].init(m*(i-1)+1,i*m-1);
s[0].init(m,m);
For(i,2,n)s[0].insert(i*m);
}
inline void work()
{
int x,y;
ll v;
while(q--)
{
x=read<int>(),y=read<int>();
if(y==m)
{
printf("%lld\n",v=s[0].find_ans(x));
s[0].insert(v);
}
else
{
printf("%lld\n",v=s[x].find_ans(y));
s[x].insert(s[0].find_ans(x));
s[0].insert(v);
}
}
}
int main()
{
file();
input();
init();
work();
return 0;
}

NOIP2017 Line up (phalanx) More related articles on problem solving report

  1. NOIP2017 Problem solving report of popularization group

    Just finished NOIP2017 Universal , I only took the exam 210, So I was upset , Write down this problem solving report ...( flee My first blog , at dalao Let's give more guidance ( membrane The first question is score, By the end helloworld I think all of you can do it , A lot of people before ...

  2. [NOIP2017] have a stroll in the park Problem solving report (DP)

    I hate to say In my AC I typed the code , But there's no way . strange 8,9 A little bit RE. But even if it's a clock ... It took me a long time . This is probably NOIP2017 The most difficult question , In order to make it easier for people who don't understand , The answer to this question will be more detailed my ...

  3. sprint Noip2017 Simulation game 5 Problem solving report —— Fifty hazel mango sauce

    1. Common divisor (gcd) [ Problem description ] Given a positive integer , stay [,n] Within the scope of , Find out how many pairs of ordinals there are (a,b) Satisfy gcd(a,b)=a xor b. [ Input format ] Enter a total of one line , A positive integer n. [ Output format ] ...

  4. sprint Noip2017 Simulation game 3 Problem solving report —— Fifty hazel mango sauce

    topic 1   prime number [ Problem description ] Given a positive integer N, inquiry 1 To N How many primes are there in . [ Input format ]primenum.in A positive integer N. [ Output format ]primenum.out a number Ans, Express 1 To N How many vegetarians are there ...

  5. sprint Noip2017 Simulation game 2 Problem solving report —— Fifty hazel mango sauce

    topic 1 Cattle running (running) [ Title Description ] New cattle to the army ,CG They are required to run every morning , from A The farm ran to B The farm . from A Farm to B There are... On the farm n- A road junction , Mark them separately ,A The farm is for Number ,B The farm is for ...

  6. sprint Noip2017 Simulation game 1 Problem solving report —— Fifty hazel mango sauce

    topic 1 Chess (chess) [ Problem description ] Yes N I'm going to take part in a chess game , The game is going on K A game of chess . Everyone can attend at most 2 A game of chess , At least 0 A game of chess . Everyone has a different level from everyone else ( Use a positive integer to represent ). In the face of ...

  7. [NOIP2017] Line up offline +SBT

    [NOIP2017] Line up Title Description Sylvia She is a woman who loves learning * children . Some time ago ,Sylvia Took part in the military training of the school . as everyone knows , We need to stand in a square array during military training . Sylvia There are n×m Famous student , Matrix ...

  8. CH Round #56 - National Day Happy competition problem solving report

    lately CH There are a lot of games on the table , I will write all the problem-solving reports here , Let's talk about the methods and skills of solving problems . T1 Magic forest describe Cortana Came to a magic forest , This forest can be seen as a N*M Matrix , There is a tree at each position in the matrix ...

  9. The second mock exam 13day1 Problem solving report

    The second mock exam 13day1 Problem solving report T1. transmitting station (station) N A launch station , Every launch station has a height hi, Transmit signal strength vi, The signal of each transmitting station will only be received by the first one higher than him on the left and right . Now look for the transmitter with the strongest signal . It took me time to recover ...

  10. BZOJ 1051 The most popular cattle Problem solving report

    The topic is right here ! 1051: [HAOI2006] Popular cattle Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 4438  Solved: 2353[S ...

Random recommendation

  1. mssql Get the start and increment of auto increment column

    -- First create a table CREATE TABLE [dbo].[abcd]( ,) NOT NULL, ) NULL, ) NULL ) ON [PRIMARY] -- Get the starting value SELECT IDENT ...

  2. MySql Study ( 5、 ... and ) —— Database optimization theory ( One )

    One . Database management system Database management system (Database Management System, DBMS) Whether it's a database or not : ACID: It means in the database management system (DBMS) There are four characteristics of Chinese accounting firms : 1 ...

  3. Yes cookie Block direct access to the next... By entering an address html, But when you enter the address directly , It'll flash to the next page , What's the matter ????、

    describe : Made two pages login.html   index.html   stay index Of body added onload event , A call to a js,js There is cookie The judgment of the , Prevent opening without logging in index.html, If not ...

  4. MFC MessageBox AfxMessageBox

    MessageBox One . Message box is a very common control , There are many attributes , This article lists some of its common methods , And some applications of it are pointed out .1.MessageBox(" This is the simplest message box !");2.M ...

  5. ( turn ) One a day Linux command (4): mkdir

    http://www.cnblogs.com/peida/archive/2012/10/25/2738271.html linux mkdir  The command is used to create a directory with the specified name , The user who created the directory is required to ...

  6. mac mysql install

    One . install 1. Download the package and install it directly : http://rj.baidu.com/soft/detail/25675.html?ald After installation root The default password is empty : Two . Change Password Changing the password directly will prompt ...

  7. MacBook The whole configuration process , For a new start MacBook Classmate

    It's recorded here MacBook The whole configuration process of , It's for a new start MacBook And feel MacBook It's hard to use for reference . 1. Peripheral expansion The characteristic of notebook is easy to carry , The disadvantage is that the screen is too small , Therefore, you need to apply for another add-on first ...

  8. ( turn )Spring Boot ( Ten ): The mail service

    http://www.ityouknow.com/springboot/2017/05/06/spring-boot-mail.html Spring Boot It's still going crazy , I didn't pay attention for more than a few months , present ...

  9. Http Request header X-Requested-With The meaning of

    When I looked at the code yesterday , See this sentence String requestedWith = ((HttpServletRequest) request).getHeader("X-Requested-W ...

  10. Two ways to serialize Serializable Parcelable

    original text :https://blog.csdn.net/hacker_crazy/article/details/80840868 One .Serializable 1.Serializable yes java Preface ...