论蒟蒻如何被cf虐
以下是身败名裂后的题解菌===========
Div1 A.Watchmen
有n个点，每个点有一个坐标。求曼哈顿距离=欧几里得距离的点对数量。
只需要统计x或y一样的点对数量。容斥即可。注意long long。（sad story
//By zzq
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <set>
#include <map>
using namespace std;
int n;
typedef long long ll;
pair<int,int> sb[233333];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&sb[i].first,&sb[i].second);
sort(sb+1,sb+1+n);
ll x=0,y=0,xy=0;
for(int i=1;i<=n;i++)
{
int tot;
for(int j=i;j<=n;j++)
{
if(sb[j].first!=sb[i].first||sb[j].second!=sb[i].second) break;
tot=j;
}
xy+=(ll)(tot-i)*(tot-i+1)/2;
i=tot;
}
for(int i=1;i<=n;i++)
{
int tot;
for(int j=i;j<=n;j++)
{
if(sb[j].first!=sb[i].first) break;
tot=j;
}
x+=(ll)(tot-i)*(tot-i+1)/2;
i=tot;
}
for(int i=1;i<=n;i++) swap(sb[i].first,sb[i].second);
sort(sb+1,sb+1+n);
for(int i=1;i<=n;i++)
{
int tot;
for(int j=i;j<=n;j++)
{
if(sb[j].first!=sb[i].first) break;
tot=j;
}
y+=(ll)(tot-i)*(tot-i+1)/2;
i=tot;
}
cout<<x+y-xy<<"\n";
}
Div1 B.Image Preview
你的手机上有n张照片，相册是那种翻页的，也就是说你从i张照片向右翻，如果i=n，就会翻到第一张，否则翻到i+1张，向左翻类似。你翻一张照片要a的时间，然后有一些照片是横着的（w），有些是竖着的（h），如果照片是横着的，那么看前就要先旋转，旋转一张要b的时间。看一张照片要1的时间。开始你打开了第一张照片，你每打开一张没看过的照片就必须要看掉，总共有T的时间，问你最多能看几张照片。
题解：
比如n=7：1 2 3 4 5 6 7
可能会有如下几种方法是最优的：
(1) 1 2 3 4 5 类似这样从左往右直接看
(2) 1 2 3 2 1 7 6 5 先往右看几张，往回翻，再从n张开始往回看
(3) 1 7 6 5 6 7 1 2 3 看完第一张，先往左翻，往回看几张，再翻回第一张，再往右看几张
然后我们只要预处理出从第一张开始往后多少张要花多少时间，从最后一张往前多少张要花多少时间，然后分这三种情况二分或者尺取即可。因为懒所以用了二分…（最后交了五六次才过）
//By zzq
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
ll n,a,b,T,sl[2333333],sr[2333333];
char w[233333];
int main()
{
scanf("%I64d%I64d%I64d%I64d",&n,&a,&b,&T);
scanf("%s",w+1);
int ans=0;
{
ll ct=0;
for(int i=1;i<=n;i++)
{
char cp=w[i]; ll tm=1+a;
if(cp=='w') tm+=b;
ct+=tm; sl[i]=ct;
if(ct-a<=T) ans=max(ans,i);
}
}
{
ll ct=0;
for(int i=n;i>=1;i--)
{
char cp=w[i]; ll tm=1+a;
if(cp=='w') tm+=b;
ct+=tm; sr[i]=ct;
}
}
for(int i=1;i<=n;i++)
{
ll zbt=sl[i]+(i-2)*a;
if(zbt>T) continue;
int l=i+1,r=n+1;
while(l<r)
{
int mid=(l+r)>>1;
ll ct=zbt+sr[mid];
if(ct<=T) r=mid; else l=mid+1;
}
if(r==n+1) continue;
ans=max(ans,int(n-l+1+i));
}
for(int i=1;i<=n;i++)
{
ll zbt=sr[i]+(n-i)*a;
if(zbt>T) continue;
int l=0,r=i-1;
while(l<r)
{
int mid=(l+r+1)>>1;
ll ct=zbt+sl[mid];
if(ct<=T) l=mid; else r=mid-1;
}
if(r==0) continue;
ans=max(ans,int(n-i+1+l));
}
printf("%d\n",ans);
}
Div1 C.Table Compression
给你一个n*m的矩阵a，里面都是正整数，求一个正整数矩阵b使b中的最大数最小。对于每一行，a和b的相对顺序不变（即对于第i行，如果a[i][x]<a[i][y]，那么b[i][x]<b[i][y]，如果a[i][x]=a[i][y]，那么b[i][x]=b[i][y]，如果a[i][x]>a[i][y]，那么b[i][x]>b[i][y]），每一列的相对顺序也不变。求一个最大数最小的b，多解输出任意一个。
每行每列排序，并查集缩一样的点，然后小于号连边，缩成DAG，跑一个类似拓扑排序的记忆化搜索即可。（我真的不知道怎么称呼这玩意儿
//By zzq
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <set>
#include <map>
using namespace std;
#define SZ 4333333
int n,m,gf[SZ],a[SZ];
#define ID(i,j) (((i)-1)*m+(j)-1)
typedef pair<int,int> pii;
pii ps[SZ];
int ff(int x) {return gf[x]?gf[x]=ff(gf[x]):x;}
void unionn(int a,int b)
{
int ga=ff(a),gb=ff(b);
if(ga!=gb) gf[ga]=gb;
}
int M=0,ma[SZ],mb[SZ];
int MM=0,fst[SZ],nxt[SZ],vb[SZ];
void adde(int a,int b)
{
++MM; nxt[MM]=fst[a]; fst[a]=MM; vb[MM]=b;
}
int dep[SZ]; bool vis[SZ];
int gd(int x)
{
if(vis[x]) return dep[x];
int mn=0;
for(int e=fst[x];e;e=nxt[e])
{
int b=vb[e];
mn=max(mn,gd(b));
}
vis[x]=1; return dep[x]=mn+1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) scanf("%d",&a[ID(i,j)]);
}
for(int i=1;i<=n;i++)
{
int pn=0;
for(int j=1;j<=m;j++) ps[++pn]=pii(a[ID(i,j)],j);
sort(ps+1,ps+1+pn);
for(int j=2;j<=pn;j++)
{
pii lst=ps[j-1],cur=ps[j];
int i1=ID(i,lst.second),i2=ID(i,cur.second);
if(lst.first==cur.first) unionn(i1,i2);
else ++M, ma[M]=i2, mb[M]=i1; //i1<i2
}
}
for(int j=1;j<=m;j++)
{
int pn=0;
for(int i=1;i<=n;i++) ps[++pn]=pii(a[ID(i,j)],i);
sort(ps+1,ps+1+pn);
for(int i=2;i<=pn;i++)
{
pii lst=ps[i-1],cur=ps[i];
int i1=ID(lst.second,j),i2=ID(cur.second,j);
if(lst.first==cur.first) unionn(i1,i2);
else ++M, ma[M]=i2, mb[M]=i1; //i1<i2
}
}
for(int i=1;i<=M;i++)
{
int a=ma[i],b=mb[i];
int f1=ff(a),f2=ff(b);
adde(f1,f2);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) gd(ff(ID(i,j)));
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++) printf("%d ",dep[ff(ID(i,j))]);
printf("\n");
}
}
Div1 D.Zip-line
给一个长度为n的序列h和m次询问。每次询问要求把一个位置上的数改成某一个值，询问LIS。询问互相独立。
考虑新的LIS中存不存在被修改的元素。
如果存在。因为询问可以离线，我们把询问排个序，在求LIS的时候顺便求一下带上这个修改后的元素的LIS。
如果不存在。如果LIS必须经过这个元素，那么长度就会-1，否则不变。
我们用L[i]表示以i结尾的LIS长度，R[i]表示以i开头的LIS长度。
那么设整个序列LIS为p，如果L[x]+R[x]-1=p那么x至少在一个LIS中对吧。那么如果x至少存在于一个LIS中且不存在其他的j使得L[j]=L[x]，那么LIS的第L[x]位就必须为x。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <limits>
#include <set>
#include <map>
using namespace std;
int inf=1000000000;
#define SZ 666666
int n,a[SZ],len,lt[SZ],L[SZ],R[SZ],q,ql[SZ],qr[SZ],col[SZ];
struct Tuple {int a,b,id;} qs[SZ];
bool c1(Tuple a,Tuple b) {return a.a<b.a;}
bool c2(Tuple a,Tuple b) {return a.a>b.a;}
bool c3(Tuple a,Tuple b) {return a.id<b.id;}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%d",a+i);
for(int i=1;i<=q;i++) scanf("%d %d",&qs[i].a,&qs[i].b), qs[i].id=i;
int cur;
sort(qs+1,qs+1+q,c1);
cur=1; len=0;
memset(lt,0,sizeof(lt));
for(int i=1;i<=n;i++)
{
int cl;
while(cur<=q&&qs[cur].a==i)
{
int ans,c=qs[cur].b;
if(!len||c>lt[len]) ans=len+1;
else ans=lower_bound(lt+1,lt+1+len,c)-lt;
ql[qs[cur].id]=ans;
++cur;
}
if(i!=1)
{
if(a[i]>lt[len]) lt[cl=++len]=a[i];
else lt[cl=lower_bound(lt+1,lt+1+len,a[i])-lt]=a[i];
}
else lt[1]=a[1], cl=1, len=1;
L[i]=cl;
}
int lis=len;
sort(qs+1,qs+1+q,c2);
for(int i=1;i<=n;i++) a[i]=inf-a[i];
cur=1; len=0;
memset(lt,0,sizeof(lt));
for(int i=n;i>=1;i--)
{
int cl;
while(cur<=q&&qs[cur].a==i)
{
int ans,c=inf-qs[cur].b;
if(!len||c>lt[len]) ans=len+1;
else ans=lower_bound(lt+1,lt+1+len,c)-lt;
qr[qs[cur].id]=ans;
++cur;
}
if(i!=n)
{
if(a[i]>lt[len]) lt[cl=++len]=a[i];
else lt[cl=lower_bound(lt+1,lt+1+len,a[i])-lt]=a[i];
}
else lt[1]=a[n], cl=1, len=1;
R[i]=cl;
}
for(int i=1;i<=n;i++)
{
if(L[i]+R[i]-1!=lis) continue;
col[L[i]]++;
}
sort(qs+1,qs+1+q,c3);
for(int p=1;p<=q;p++)
{
int i=qs[p].a;
int a1=ql[p]+qr[p]-1;
bool met=L[i]+R[i]-1==lis&&col[L[i]]==1;
int a2=lis-met;
printf("%d\n",max(a1,a2));
}
}
E题施工中…