这是一个古老的坑了。孩子真不会分治怎么办（雾
去LOJ上扒了几道题做 主要就是纯分治和CDQ分治 反而点分治 陈老师二分还有分治FFT都还会亚子（我丢 我好难
JOISC2014 Day 3 稻草人
分治以后考虑维护上方的递增单调栈，下方的递减单调栈，然后二分位置确定每一个答案就好了。
//Love and Freedom. #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define ll long long #define inf 20021225 #define N 200010 using namespace std; int read() { int s=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return f*s; } struct poi{int x,y;}p[N]; bool cmpx(poi a,poi b){return a.x<b.x;} bool cmpy(poi a,poi b){return a.y<b.y;} int stk1[N],stk2[N],n1,n2; ll fin; void solve(int l,int r) { if(l==r) return; int mid=l+r>>1; solve(l,mid); solve(mid+1,r); sort(p+l,p+mid+1,cmpx); sort(p+mid+1,p+r+1,cmpx); int j=l; n1=n2=0; for(int i=mid+1;i<=r;i++) { while(n2 && p[i].y<p[stk2[n2]].y) n2--; stk2[++n2]=i; while(j<=mid && p[j].x<p[i].x) { while(n1 && p[j].y>p[stk1[n1]].y) n1--; stk1[++n1]=j; j++; } int lpos=1,rpos=n1,ans=0; while(lpos<=rpos) { int mid=lpos+rpos>>1; if(p[stk1[mid]].x>p[stk2[n2-1]].x) ans=mid,rpos=mid-1; else lpos=mid+1; } if(ans) fin+=n1-ans+1; } } int main() { int n=read(); for(int i=1;i<=n;i++) p[i].x=read(),p[i].y=read(); p[0].x=p[0].y=-1; sort(p+1,p+n+1,cmpy); solve(1,n); printf("%lld\n",fin); return 0; }
「TJOI / HEOI2016」序列
朴素DP长这样
$f[i] = max(f[i],f[j]+1)$
$i>j$ $a[i]>=mx[j]$ $mn[i]>=a[j]$
一眼三维偏序上CDQ就好啦
好像裸上树套树的人更多（毒瘤！
//Love and Freedom. #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define ll long long #define inf 20021225 #define N 100010 #define lowbit(x) (x&-x) using namespace std; int read() { int s=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return f*s; } struct node{int a,mx,mn,f,id;}a[N]; struct bit { int t[N],n; void mfy(int x,int v){while(x<=n) t[x]=max(t[x],v),x+=lowbit(x);} int qry(int x){int ans=0; while(x) ans=max(ans,t[x]),x-=lowbit(x); return ans;} void del(int x){while(x<=n) t[x]=0,x+=lowbit(x);} }b; bool cmpi(node x,node y){return x.id<y.id;} bool cmpa(node x,node y){return x.a<y.a;} bool cmpn(node x,node y){return x.mn<y.mn;} void solve(int l,int r) { if(l==r) return; int mid=l+r>>1; solve(l,mid); sort(a+l,a+mid+1,cmpa); sort(a+mid+1,a+r+1,cmpn); int w=l; for(int i=mid+1;i<=r;i++) { while(w<=mid && a[w].a<=a[i].mn) b.mfy(a[w].mx,a[w].f),w++; a[i].f=max(a[i].f,b.qry(a[i].a)+1); } for(int i=l;i<w;i++) b.del(a[i].mx); sort(a+mid+1,a+r+1,cmpi); solve(mid+1,r); } int main() { int n=read(),m=read(); b.n=n; for(int i=1;i<=n;i++) a[i].mn=a[i].mx=a[i].a=read(),a[i].id=i,a[i].f=1; for(int i=1;i<=m;i++) { int x=read(),v=read(); a[x].mx=max(a[x].mx,v); a[x].mn=min(a[x].mn,v); } solve(1,n); int ans=0; for(int i=1;i<=n;i++) ans=max(ans,a[i].f); printf("%d\n",ans); return 0; }
【BZOJ2989】数列
看起来有两个绝对值能想到什么呢！曼哈顿距离！
简单的转欧式距离就是二维数点啦！
//Love and Freedom. #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define ll long long #define inf 20021225 #define N 600010 #define nd 250010 #define lowbit(x) (x&-x) using namespace std; int read() { int s=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return f*s; } struct bit { int t[N],n; void modify(int x,int v){while(x<=n) t[x]+=v,x+=lowbit(x);} int query(int x){int ans=0; while(x) ans+=t[x],x-=lowbit(x); return ans;} int ask(int x,int y){return query(y)-query(x-1);} }b; struct node{int type,x,y,k,id;}a[N],tmp[N]; bool cmpx(node x,node y){return x.x==y.x?x.type>y.type:x.x<y.x;} int f[N]; void solve(int l,int r) { if(l==r) return; int mid=l+r>>1,t=0; solve(l,mid); for(int i=l;i<=mid;i++) if(!a[i].type) tmp[++t]=a[i]; for(int i=mid+1;i<=r;i++) if(a[i].type) { tmp[++t]=(node){+1,a[i].x-a[i].k,a[i].y,a[i].k,a[i].id}; tmp[++t]=(node){-1,a[i].x+a[i].k,a[i].y,a[i].k,a[i].id}; } sort(tmp+1,tmp+t+1,cmpx); for(int i=1;i<=t;i++) if(!tmp[i].type) b.modify(tmp[i].y,1); else f[tmp[i].id]-=tmp[i].type*b.ask(tmp[i].y-tmp[i].k,tmp[i].y+tmp[i].k); for(int i=1;i<=t;i++) if(!tmp[i].type) b.modify(tmp[i].y,-1); solve(mid+1,r); } int top,v[N],fq; char ch[20]; int main() { int n=read(),q=read(),x,y; for(int i=1;i<=n;i++) v[i]=read(),a[++top]=(node){0,i+v[i],i-v[i]+nd,0,0}; for(int i=1;i<=q;i++) { scanf("%s",ch); x=read(),y=read(); if(ch[0]=='Q') a[++top]=(node){1,x+v[x],x-v[x]+nd,y,++fq}; else v[x]=y,a[++top]=(node){0,x+v[x],x-v[x]+nd,0,0}; } b.n=nd+nd; solve(1,top); for(int i=1;i<=fq;i++) printf("%d\n",f[i]); return 0; }
今天才写了3题...太慢了...
晚上考试...孩子累了...