#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\n",ans[i]);
/*for (register int i=1;i<=n;++i)
f[ans[i]]++;
for (register int i=0;i<n;++i)
printf("%d\n",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\n",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\n",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\n",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\n",z);
y-=lowbit(y);
}
x-=lowbit(x);
}
//printf("%d\n",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\n",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\n",ans);
return 0;
}
[NOI2007]货币兑换
题意不想描述，写的很清晰了。。。
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\n",f[n]);
return 0;
}