day1
t1的结论貌似在哪见过，自己稍微验证了一下貌似没记错就没有管了。
t2一道很好(keng)的模拟题啊
t3自己做题好慢啊，想出来dp打上去最后几分钟才过了大样例，我写的是记忆化搜索，判-1很好判，没时间加上去了可惜了，不过还是自己做题太慢了。然后由于没拍，不确定自己dp对不对，就特判了k=0粘了一个暴力，没想到暴力错了，70变成50…基础不扎实gg

100+100+50=250  好菜啊t3没A掉

day2
t1看完题就开始打，没注意算距离时减一下就变成两倍了会爆long long，但好像数据中z都>=0 ??
t2写完搜索后发现好像可以把所有点深度变成一个n进制数，可以记忆化，不过打完发现n=12要跑10s+，果断删掉换成爆搜。并没有想到如何状压…
t3打完前50分后有一个想法，打完后发现自己想的是错的，于是老老实实写x=1的30分，但耗费了好多时间，没时间打出个数据结构了，于是用了vector，还以为vector有多快，CCF的老爷机上1e5都跑不过，于是t3就挂了，暴力分都没拿全。

100+70+50=220 太菜了…

自己做较难题不行，另外noip中还犯了很多知识性错误，主要原因是学的不扎实，接下来的比赛加油吧。

题解

day1

t1 答案就是x*y-x-y，证明可以见usaco4.1麦香牛块的题解。貌似此题坑到了我校不少选手。

t2 细心模拟即可。

t3 设f(i,j)表示到i点从1~i距离为dis[i]+j的路径个数。对于边u->v，有dis[v]+jv=dis[u]+ju+w(u,v)，所以$f(v,j_v)=\sum_{u->v}f(u,dis[v]-dis[u]-w(u,v)-j_v)$，具体实现可以建出反图记忆化搜索，答案为-1当且仅当同一状态在dfs栈中出现了两次。

day2

t1 建图后bfs判联通。

t2 f1(i,s)表示点i到集合s中点的最小权值，这个可以O(n^2*2^n)处理出。 f2(s1,s2)表示集合s2与s1相连花费的最小代价，O(n*3^n)处理。

f(i,s)表示已经确定了深度<=i的点，且这些点的集合为s，将来要付出的最小代价，枚举下一层选哪些点，f(i,s)=min{ f(i+1,s|s')+f2(s,s') }，虽然s‘可能会连向深度<i的点，但如果这样转移了答案会变大，而且如果真要这样连，之前就会转移了的，所以不会计算出错的答案也不会漏掉最优解，这一部分复杂度是O(n*3^n)的。

t3 x=1可以用线段树完成，只需记当前区间未被删除的点的个数，删除第k个数直接查到删去即可，插入同理。

对于一般情况可以对每一排的前m-1个元素建出线段树，然后对最后一列再建出线段树，操作和x=1是一样的，但发现空间开不下，因为这n+1棵线段树最开始叶子节点是等差数列，所以动态开点即可。

附d2t3代码(巨难看)

#include
#include
#include
#include
#include
#include
#include
#define P puts("lala")
#define cp cerr<<"lala"< pii;
inline void read(int &re)
{
char ch=getchar();int g=1;
while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();}
re=0;
while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+ch-48,ch=getchar(); re*=g; } typedef long long ll; inline void read(ll &re) { char ch=getchar();ll g=1; while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();}
re=0;
while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+ch-48,ch=getchar();
re*=g;
}

const int N=300050;
int n,m,q;
int rt[N],ch[N*80][2],siz[N*80],sz=0;
ll val[N*80];

ll kth_las(int o,int l,int r,int k)
{
if(l==r) {return val[o];}
int mid=l+r>>1;
if(!ch[o][0])
{
ch[o][0]=++sz;ch[o][1]=++sz;
siz[ch[o][0]]=(siz[o]+1)>>1; siz[ch[o][1]]=siz[o]>>1;
if(l==mid) val[ch[o][0]]=(ll)l*m;
if(mid+1==r) val[ch[o][1]]=(ll)r*m;
}
if(k<=siz[ch[o][0]]) return kth_las(ch[o][0],l,mid,k);
else return kth_las(ch[o][1],mid+1,r,k-siz[ch[o][0]]);
}

ll kth(int o,int l,int r,int k,int wh)
{
if(l==r) {return val[o];}
int mid=l+r>>1;
if(!ch[o][0])
{
ch[o][0]=++sz;ch[o][1]=++sz;
siz[ch[o][0]]=(siz[o]+1)>>1; siz[ch[o][1]]=siz[o]>>1;
if(l==mid) val[ch[o][0]]=(ll)(wh-1ll)*m+l;
if(mid+1==r) val[ch[o][1]]=(ll)(wh-1ll)*m+r;
}
if(k<=siz[ch[o][0]]) return kth(ch[o][0],l,mid,k,wh);
else return kth(ch[o][1],mid+1,r,k-siz[ch[o][0]],wh);
}

void del(int o,int l,int r,int k)
{
if(l==r) {siz[o]=0;val[o]=0;return ;}
int mid=l+r>>1;
if(k<=siz[ch[o][0]]) del(ch[o][0],l,mid,k);
else del(ch[o][1],mid+1,r,k-siz[ch[o][0]]);
siz[o]=siz[ch[o][0]]+siz[ch[o][1]];
}

void ins_las(int o,int l,int r,int x,ll k)
{
if(l==r) {siz[o]=1;val[o]=k;return ;}
int mid=l+r>>1;
if(!ch[o][0])
{
ch[o][0]=++sz;ch[o][1]=++sz;
siz[ch[o][0]]=(siz[o]+1)>>1; siz[ch[o][1]]=siz[o]>>1;
if(l==mid) val[ch[o][0]]=(ll)l*m;
if(mid+1==r) val[ch[o][1]]=(ll)r*m;
}
if(x<=siz[ch[o][0]]) ins_las(ch[o][0],l,mid,x,k);
else ins_las(ch[o][1],mid+1,r,x-siz[ch[o][0]],k);
siz[o]=siz[ch[o][0]]+siz[ch[o][1]];
}

void ins(int o,int l,int r,int x,ll k,int wh)
{
if(l==r) {siz[o]=1;val[o]=k;return ;}
int mid=l+r>>1;
if(!ch[o][0])
{
ch[o][0]=++sz;ch[o][1]=++sz;
siz[ch[o][0]]=(siz[o]+1)>>1; siz[ch[o][1]]=siz[o]>>1;
if(l==mid) val[ch[o][0]]=(ll)(wh-1ll)*m+l;
if(mid+1==r) val[ch[o][1]]=(ll)(wh-1ll)*m+r;
}
if(x<=siz[ch[o][0]]) ins(ch[o][0],l,mid,x,k,wh);
else ins(ch[o][1],mid+1,r,x-siz[ch[o][0]],k,wh);
siz[o]=siz[ch[o][0]]+siz[ch[o][1]];
}

void wj()
{
freopen("phalanx.in","r",stdin);
freopen("phalanx.out","w",stdout);
}
int main()
{
wj();
int i,j,opt,T;
read(n);read(m);read(q);
for(i=1;i<=n;++i) { rt[i]=++sz;siz[rt[i]]=m-1+q; ch[rt[i]][0]=++sz; ch[rt[i]][1]=++sz; siz[ch[rt[i]][0]]=(siz[rt[i]]+1)>>1; siz[ch[rt[i]][1]]=siz[rt[i]]>>1;
}

rt\[n+1\]=++sz;siz\[rt\[n+1\]\]=n+q;  
ch\[rt\[n+1\]\]\[0\]=++sz; ch\[rt\[n+1\]\]\[1\]=++sz;  
siz\[ch\[rt\[n+1\]\]\[0\]\]=(siz\[rt\[n+1\]\]+1)>>1; siz\[ch\[rt\[n+1\]\]\[1\]\]=siz\[rt\[n+1\]\]>>1;

for(int cas=1;cas<=q;++cas)  
{  
    int x,y;read(x);read(y);  
    if(y==m)  
    {  
        ll o=kth\_las(rt\[n+1\],1,n+q,x);  
        del(rt\[n+1\],1,n+q,x);  
        printf("%lld\\n",o);  
        ins\_las(rt\[n+1\],1,n+q,n,o);  
    }  
    else  
    {  
        ll o=kth(rt\[x\],1,m-1+q,y,x);  
        del(rt\[x\],1,m-1+q,y);  
        printf("%lld\\n",o);//get (x,y)

        ll las=kth\_las(rt\[n+1\],1,n+q,x);//get the last element and push it to the xth row  
        ins(rt\[x\],1,m-1+q,m-1,las,x);

        del(rt\[n+1\],1,n+q,x);//push o to the last column  
        ins\_las(rt\[n+1\],1,n+q,n,o);  
    }  
}  
return 0;  

}