cdq分治（hdu 5618 Jam's problem again[陌上花开]、CQOI 2011 动态逆序对、hdu 4742 Pinball Game、hdu 4456 Crowd、[HEOI2016/TJOI2016]序列、[NOI2007]货币兑换 ） [NOI2007]货币兑换
#include <bits/stdc++.h>
#define MAXN 100010
using namespace std;
int n,k,T,xx;
int ans[MAXN],c[MAXN],f[MAXN];
struct Node{
int x,y,z,id;
}a[100010],b[100010];
inline int read(){
char ch;
bool f=false;
int res=0;
while (((ch=getchar())<'0'||ch>'9')&&ch!='-');
if (ch=='-')
f=true;
else
res=ch-'0';
while ((ch=getchar())>='0'&&ch<='9')
res=(res<<3)+(res<<1)+ch-'0';
return f?~res+1:res;
}
inline bool cmp(Node x,Node y){
if (x.x==y.x){
if (x.y==y.y){
if (x.z==y.z){
return x.id<y.id;
}
else return x.z<y.z;
}
else return x.y<y.y;
}
else return x.x<y.x;
}
inline bool cmp1(Node x,Node y){
if (x.y==y.y)
return x.z<y.z;
else
return x.y<y.y;
}
inline int lowbit(int x){
return x&(-x);
}
inline void add(int x,int y){
while (x<=MAXN){
c[x]+=y,x+=lowbit(x);
}
}
inline int sum(int x){
int summ=0;
while (x>0){
summ+=c[x],x-=lowbit(x);
}
return summ;
}
void solve(int l,int r){
if (l>=r)
return;
int mid=(l+r)/2;
for (register int i=l;i<=r;i++){
b[i-l+1].x=0,b[i-l+1].y=a[i].y,b[i-l+1].z=a[i].z;
if (i>mid)
b[i-l+1].id=a[i].id;
else
b[i-l+1].id=-1;
}
sort(b+1,b+r-l+2,cmp1);
for (register int i=1;i<=r-l+1;++i)
if (b[i].id==-1)
add(b[i].z,1);
else
ans[b[i].id]+=sum(b[i].z);
for(register int i=1;i<=r-l+1;++i)
if(b[i].id==-1)
add(b[i].z,-1);
solve(l,mid);
solve(mid+1,r);
}
int main(){
//scanf("%d",&T);
T=read();
while (T--){
memset(c,0,sizeof(c));
memset(ans,0,sizeof(ans));
//scanf("%d",&n);
n=read();
for (register int i=1;i<=n;++i){
a[i].x=read(),a[i].y=read(),a[i].z=read(),a[i].id=i;
//scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
//a[i].id=i;
}
sort(a+1,a+1+n,cmp);
for (register int i=n-1;i>=1;i--){
if (a[i].x==a[i+1].x&&a[i].y==a[i+1].y&&a[i].z==a[i+1].z)
xx++;
else xx=0;
ans[a[i].id]+=xx;
}
solve(1,n);
for (register int i=1;i<=n;++i)
printf("%d
",ans[i]);
/*for (register int i=1;i<=n;++i)
f[ans[i]]++;
for (register int i=0;i<n;++i)
printf("%d
",f[i]);*/
}
return 0;
}
#include <bits/stdc++.h>
#define MAXN 100010
using namespace std;
long long n,m,sum1,x,gg;
long long ans[MAXN],f[MAXN],c[MAXN];
struct Node{
long long x,y,z,id;
}a[MAXN],b[MAXN];
inline long long read(){
char ch;
bool f=false;
long long res=0;
while (((ch=getchar())<'0'||ch>'9')&&ch!='-');
if (ch=='-')
f=true;
else
res=ch-'0';
while ((ch=getchar())>='0'&&ch<='9')
res=(res<<3)+(res<<1)+ch-'0';
return f?~res+1:res;
}
inline bool cmp(Node x,Node y){
if (x.x==y.x)
return x.y<y.y;
else
return x.x<y.x;
}
inline bool cmp1(Node x,Node y){
return x.z<y.z;
}
inline long long lowbit(long long x){
return x&(-x);
}
inline void add(long long x,long long y){
while (x<=n){
c[x]+=y,x+=lowbit(x);
}
}
inline long long sum(long long x){
long long summ=0;
while (x>0){
summ+=c[x],x-=lowbit(x);
}
return summ;
}
inline void sc(long long l,long long r){
if (l>=r)
return;
long long mid=(l+r)/2;
for (register long long i=l;i<=r;++i){
b[i-l+1]=a[i];
if (i>mid) b[i-l+1].id=1;
}
sort(b+1,b+r-l+2,cmp);
for (register long long i=1;i<=r-l+1;++i){
if (b[i].id==0)
add(b[i].y,1);
else
ans[b[i].z]+=sum(n)-sum(b[i].y);
}
for (register long long i=1;i<=r-l+1;++i)
if (b[i].id==0)
add(b[i].y,-1);
for (register long long i=r-l+1;i>=1;--i){
if (b[i].id==0)
add(b[i].y,1);
else
ans[b[i].z]+=sum(b[i].y);
}
for (register long long i=r-l+1;i>=1;--i){
if (b[i].id==0)
add(b[i].y,-1);
}
sc(l,mid);
sc(mid+1,r);
}
int main(){
n=read(),m=read();gg=n;
for (register long long i=1;i<=n;++i){
a[i].x=i,a[i].y=read();
f[a[i].y]=i;
}
for (register long long i=1;i<=m;++i)
a[f[read()]].z=gg--;
for (register long long i=1;i<=n;i++)
if (a[i].z==0)
a[i].z=gg--;
sort(a+1,a+n+1,cmp1);
sc(1,n);
for (register long long i=1;i<=n;i++)
sum1+=ans[i];
for (register long long i=n;i>n-m;--i){
printf("%lld
",sum1);
sum1-=ans[i];
}
return 0;
}
Description
给出n个三维点对(x,y,z)，求三维非严格最长上升子序列长度和最长上升子序列数量
Solution
这是一个三维LIS问题，可以用CDQ解决。
先按x排序，降一维，然后剩下y、z，在y上进行CDQ分治，按y的大小用前面的更新后面的。
z方向离散化后用树状数组维护。
#include <bits/stdc++.h>
#define MAXN 100010
using namespace std;
const int Mo=1<<30;
int ans,T,n;
int dp[MAXN],fa[MAXN],q1[MAXN],q2[MAXN];
int g[MAXN<<1],p[MAXN];
long long num[MAXN],q3[MAXN],ansn;
int t1;
inline int read() {
char ch;
bool f=false;
int res=0;
while (((ch=getchar())<'0'||ch>'9')&&ch!='-');
if (ch=='-')
f=true;
else
res=ch-'0';
while ((ch=getchar())>='0'&&ch<='9')
res=(res<<3)+(res<<1)+ch-'0';
return f?~res+1:res;
}
struct Node {
int x,y,z;
}q[MAXN];
inline bool cmp(Node x,Node y) {
if (x.x!=y.x)
return x.x<y.x;
if (x.y!=y.y)
return x.y<y.y;
return x.z<y.z;
}
inline bool cmp1(int x,int y) {
if (q[x].y!=q[y].y)
return q[x].y<q[y].y;
return x<y;
}
inline int lowbit(int x) {
return x&(-x);
}
inline void add(int x,int v,long long y,int maxx) {
while (x<=maxx) {
if (v>q2[x])
q2[x]=v,q3[x]=y;
else
if (v==q2[x])
q3[x]+=y;
x+=lowbit(x);
}
}
inline int sum(int x,long long &nn) {
int summ=0;
while (x>0) {
if (summ<q2[x])
summ=q2[x],nn=q3[x];
else
if (q2[x]==summ)
nn+=q3[x];
x-=lowbit(x);
}
return summ;
}
void sc(int t,int w) {
/*if (t>w)
return;*/
if (t==w) {
if (dp[t]>ans)
ans=dp[t],ansn=num[t];
else
if (dp[t]==ans) {
ansn=ansn+num[t];
}
q1[t]=q[t].z;
return;
}
int mid=(t+w)>>1,le=t,ri=mid+1,tt1=w-t+1,maxx=mid-t+1,l,h;
memmove(g+t1,fa+t,tt1*sizeof(int));
for (int i=0;i<tt1;++i)
if (g[t1+i]<=mid)
fa[le++]=g[t1+i];
else
fa[ri++]=g[t1+i];
t1+=tt1;
sc(t,mid);
l=t1;
t1-=tt1;
for (int i=1;i<=maxx;++i)
q2[i]=0;
for (int i=t1;i<l;++i) {
if (g[i]<=mid) {
h=lower_bound(q1+t,q1+t+maxx,q[g[i]].z)-(q1+t)+1;
add(h,dp[g[i]],num[g[i]],maxx);
continue;
}
h=lower_bound(q1+t,q1+t+maxx,q[g[i]].z)-(q1+t);
if (h>=maxx||q1[t+h]>q[g[i]].z)
h--;
if (h>=0) {
long long ttt=0;
int tt=sum(h+1,ttt)+1;
if (tt>dp[g[i]])
dp[g[i]]=tt,num[g[i]]=ttt;
else
if (tt==dp[g[i]]&&tt!=1)
num[g[i]]+=ttt;
}
}
sc(mid+1,w);
merge(q1+t,q1+t+maxx,q1+t+maxx,q1+t+tt1,p);
memmove(q1+t,p,tt1*sizeof(int));
}
int main() {
T=read();
while (T--) {
n=read();
ansn=t1=ans=0;
for (int i=1;i<=n;++i)
q[i].x=read(),q[i].y=read(),q[i].z=read();
sort(q+1,q+n+1,cmp);
for (int i=1;i<=n;++i)
fa[i]=i;
for (int i=1;i<=n;++i){
dp[i]=1;
num[i]=1;
}
sort(fa+1,fa+n+1,cmp1);
sc(1,n);
printf("%d %lld
",ans,ansn%Mo);
}
return 0;
}
Description
Solution
本来想继续写cdq的（毕竟cdq专题2333）但网上一查题解发现好像写二维树状数组的人更多。
一想反正我也不会，我这么菜，那就学这个吧。（而且看起来码量小多了）
然后...我调了一上午QWQ
这题就是将矩形旋转45度，每个询问就相当于询问一个矩阵，用容斥口胡下然后用二维树状数组维护
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#define MAXN 4000010
using namespace std;
int t[MAXN],q[MAXN],p[MAXN],X[MAXN],Y[MAXN],Z[MAXN];
int k,n,m,ma;
inline int read() {
char ch;
bool f=false;
int res=0;
while (((ch=getchar())<'0'||ch>'9')&&ch!='-');
if (ch=='-')
f=true;
else
res=ch-'0';
while ((ch=getchar())>='0'&&ch<='9')
res=(res<<3)+(res<<1)+ch-'0';
return f?~res+1:res;
}
inline int find (int x) {
return lower_bound(q+1,q+k,x)-q;
}
inline int lowbit(int x) {
return x&(-x);
}
inline void Hash(int x,int y) {
int yy=y;
while (x<=ma) {
y=yy;
while (y<=ma) {
q[k++]=x*ma+y;
y+=lowbit(y);
}
x+=lowbit(x);
}
}
inline void add(int x,int y,int z) {
int yy=y;
while (x<=ma) {
y=yy;
while (y<=ma) {
//int zz=lower_bound(q+1,q+k,(x*ma+y))-q;
//t[zz]+=z;
t[find(x*ma+y)]+=z;
//printf("%d
",y);
y+=lowbit(y);
}
x+=lowbit(x);
}
}
inline int sum(int x,int y) {
int summ=0,yy=y;
while (x) {
y=yy;
while (y) {
int z=find(x*ma+y);
if (q[z]==x*ma+y)
summ+=t[z];
//printf("%d
",z);
y-=lowbit(y);
}
x-=lowbit(x);
}
//printf("%d
",summ);
return summ;
}
int main() {
while (true) {
n=read();
if (n==0)
return 0;
k=1,ma=2*n,m=read();
memset(t,0,sizeof(t));
for (int i=1;i<=m;++i){
p[i]=read(),X[i]=read(),Y[i]=read(),Z[i]=read();
if (p[i]==1)
Hash(X[i]-Y[i]+n,X[i]+Y[i]);
}
sort(q+1,q+k);
k=unique(q+1,q+k)-q;
for (int i=1;i<=m;++i){
if (p[i]==1)
add(X[i]-Y[i]+n,X[i]+Y[i],Z[i]);
else {
int a=max(1,X[i]-Y[i]+n-Z[i]);
int b=max(1,X[i]+Y[i]-Z[i]);
int c=min(ma,X[i]-Y[i]+n+Z[i]);
int d=min(ma,X[i]+Y[i]+Z[i]);
printf("%d
",sum(c,d)-sum(c,b-1)-sum(a-1,d)+sum(a-1,b-1));
}
}
}
return 0;
}
#include<bits/stdc++.h>
#define N 100010
using namespace std;
int a[N],maxx[N],minn[N],fa[N],c[N],f[N];
int num,ans,x,y,n,m;
inline int read() {
char ch;
bool f=false;
int res=0;
while (((ch=getchar())<'0'||ch>'9')&&ch!='-');
if (ch=='-')
f=true;
else
res=ch-'0';
while ((ch=getchar())>='0'&&ch<='9')
res=(res<<3)+(res<<1)+ch-'0';
return f?~res+1:res;
}
inline int lowbit(int x){
return x&(-x);
}
inline void add(int x,int y){
while (x<=num){
if (y)
c[x]=max(c[x],y);
else c[x]=0;
x+=lowbit(x);
}
}
inline int sum(int x){
int summ=0;
while (x>0){
summ=max(summ,c[x]),x-=lowbit(x);
}
return summ;
}
inline bool cmp(int x,int y){
return a[x]<a[y];
}
inline bool cmp1(int x,int y){
return minn[x]<minn[y];
}
void sc(int l,int r){
if (l==r){
if (f[l]<1)
f[l]=1;
return;
}
int mid=(l+r)>>1;
sc(l,mid);
for (int i=l;i<=r;++i)
fa[i]=i;
sort(fa+l,fa+1+mid,cmp);
sort(fa+mid+1,fa+1+r,cmp1);
for (int i=mid+1,j=l;i<=r;++i){
while (j<=mid&&a[fa[j]]<=minn[fa[i]])
add(maxx[fa[j++]],f[fa[j]]);
f[fa[i]]=max(f[fa[i]],sum(a[fa[i]])+1);
if (i==r)
for (int k=l;k<j;++k)
add(maxx[fa[k]],0);
}
sc(mid+1,r);
}
int main(){
n=read(),m=read();
for (int i=1;i<=n;++i)
a[i]=read();
for (int i=1;i<=n;++i)
maxx[i]=minn[i]=a[i];
while (m--){
x=read(),y=read();
maxx[x]=max(maxx[x],y);
minn[x]=min(minn[x],y);
}
for (int i=1;i<=n;++i)
num=max(num,a[i]);
sc(1,n);
for (int i=1;i<=n;++i)
ans=max(ans,f[i]);
printf("%d
",ans);
return 0;
}
题意不想描述，写的很清晰了。。。
Solution：
好像隐隐约约中听大佬说不止要用cdq，还要用斜率优化、splay维护....感觉好可怕
然后就搁置了两三天...（颓了两三天）
设f[i]表示前i天的最大收益。
第i天可以换成B券最大数目f[i]*(1/(Rate[i]*A[i]+B[i]))
第i天可以换成的A券最大数目f[i]*(Rate[i]/(Rate[i]*A[i]+B[i]))
第i天将第j天的券全卖掉A[i]*X(j)+B[i]*Y(j)
所以f[i]=max{f[i-1],A[i]*X(j)+B[i]*Y(j)}
则我们需要求 max p=A[i]*X(j)+B[i]*Y(j)
即我们要最大化直线方程Y(j)=-A[i]/B[i]*X(j)+p/B[j]的截距
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert> #endif #include <cctype> #include <cerrno> #include <cfloat> #include <ciso646> #include <climits> #include <clocale> #include <cmath> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #if __cplusplus >= 201103L #include <ccomplex> #include <cfenv> #include <cinttypes> #include <cstdalign> #include <cstdbool> #include <cstdint> #include <ctgmath> #include <cwchar> #include <cwctype> #endif // C++ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector> #if __cplusplus >= 201103L #include <array> #include <atomic> #include <chrono> #include <condition_variable> #include <forward_list> #include <future> #include <initializer_list> #include <mutex> #include <random> #include <ratio> #include <regex> #include <scoped_allocator> #include <system_error> #include <thread> #include <tuple> #include <typeindex> #include <type_traits> #include <unordered_map> #include <unordered_set> #endif using namespace std; const int MAXN=100010; const double inf=1e20,Inf=1e-8; struct Node { double x,y,a,b,k,z; int num; }p[MAXN],tt[MAXN]; int a[MAXN],n,cnt; double f[MAXN]; inline bool cmp(Node x,Node y) { return x.k>y.k; } inline int read() { char ch; bool f=false; int res=0; while (((ch=getchar())<'0'||ch>'9')&&ch!='-'); if (ch=='-') f=true; else res=ch-'0'; while ((ch=getchar())>='0'&&ch<='9') res=(res<<3)+(res<<1)+ch-'0'; return f?~res+1:res; } inline double pd(int a,int b){ if (!b) return -inf; else if (fabs(p[a].x-p[b].x)<Inf) return inf; else return (p[b].y-p[a].y)/(p[b].x-p[a].x); } void sc(int t,int w){ int mid=(t+w)>>1; if (t==w){ if (f[t-1]>f[t]) f[t]=f[t-1]; p[t].y=f[t]/(p[t].a*p[t].z+p[t].b); p[t].x=p[t].y*p[t].z; return; } int j=1,cnt1=t,cnt2=mid+1; for (int i=t;i<=w;++i) if (p[i].num<=mid) tt[cnt1++]=p[i]; else tt[cnt2++]=p[i]; for (int i=t;i<=w;++i) p[i]=tt[i]; sc(t,mid); cnt=0; for (int i=t;i<=mid;++i){ while (cnt>1&&pd(a[cnt-1],a[cnt])<pd(a[cnt-1],i)+Inf) cnt--; a[++cnt]=i; } for(int i=mid+1;i<=w;i++) { while(j<cnt&&pd(a[j],a[j+1])+Inf>p[i].k) j++; f[p[i].num]=max(f[p[i].num],p[a[j]].x*p[i].a+p[a[j]].y*p[i].b); } sc(mid+1,w); int t1=t,ww1=mid+1; for(int i=t;i<=w;i++) { if(((p[t1].x<p[ww1].x||(fabs(p[t1].x-p[ww1].x)<Inf&&p[t1].y<p[ww1].y))||ww1>w)&&t1<=mid) tt[i]=p[t1++]; else tt[i]=p[ww1++]; } for(int i=t;i<=w;i++) p[i]=tt[i]; } int main(){ n=read(); scanf("%lf",&f[0]); for (int i=1;i<=n;++i){ scanf("%lf%lf%lf",&p[i].a,&p[i].b,&p[i].z); p[i].k=-p[i].a/p[i].b; p[i].num=i; } sort(p+1,p+n+1,cmp); sc(1,n); printf("%.3lf ",f[n]); return 0; }