题意：一棵n个结点的完全二叉树，初始i号结点的权值为i。有两种操作：单点修改；询问经过某个结点的路径中，权值和最大的路径的权值和是多少。
修改的时候，暴力修改到根节点的路径上的点的f(x)即可。
跟虚树的思想只是有点点像而已，实际上不是一个东西啦。
队友的代码：
#include#include #include #include #include using namespace std;struct nod{int lx,d;long long c;}q[110000];struct nod2{int sum[40],s[40],l;}ceng;int ls[2800000],i,n,m,all,wei[40];long long t[2800000],v[2800000];char s[100];int fen(int a){ if (a==0) return 0; int l=1,r=all,mid; while (l!=r) { mid=(l+r)/2; if (ls[mid]>=a) r=mid; else l=mid+1; } return l;}void add(int a){ while (a) { ls[++all]=a; a=a/2; }}void quchong(){ int l,r,now=0; l=1; while (l<=all) { r=l; while (r<=all && ls[l]==ls[r]) r++; ls[++now]=ls[l]; l=r; } all=now;}long long getv(int d){ if (d>n) return 0; int k=fen(d),c,y,ans; if (ls[k]==d) return t[k]; y=d; c=0; while (y!=0) { c++; y=y/2; } if (d==ceng.s[c]) return ceng.sum[c]; ans=0; y=d; while (y<=n) { ans+=y; y=y*2+1; } return ans;}void modify(int d,long long a){ d=fen(d); v[d]=a; while (d!=0) { t[d]=max(getv(ls[d]*2),getv(ls[d]*2+1))+v[d]; d=fen(ls[d]/2); }}void getceng(int d){ int i; ceng.l=0; while (d) { ceng.s[++ceng.l]=d; d=d/2; } for (i=1;i<=ceng.l/2;i++) swap(ceng.s[i],ceng.s[ceng.l-i+1]); ceng.sum[ceng.l]=ceng.s[ceng.l]; for (i=ceng.l-1;i>=1;i--) ceng.sum[i]=ceng.s[i]+ceng.sum[i+1];}long long getans(int d){ long long ans,p,sum=0; int pre; d=fen(d); p=t[d]; ans=getv(ls[d]*2)+getv(ls[d]*2+1)+v[d]; pre=d; d=fen(ls[d]/2); while (d) { sum+=v[d]; if (ls[d]*2==ls[pre]) ans=max(ans,p+sum+getv(ls[d]*2+1)); else ans=max(ans,p+sum+getv(ls[d]*2)); pre=d; d=fen(ls[d]/2); } return ans;}void chushi(){ int i; for (i=all;i>=1;i--) { v[i]=ls[i]; t[i]=max(getv(ls[i]*2),getv(ls[i]*2+1))+v[i]; }}int main(){ wei[0]=1; for (i=1;i<=30;i++) wei[i]=wei[i-1]*2; while (scanf("%d%d",&n,&m)!=EOF) { all=0; getceng(n); for (i=1;i<=m;i++) { scanf("%s",&s); if (s[0]=='q') { scanf("%d",&q[i].d); q[i].lx=0; } if (s[0]=='c') { scanf("%d%lld",&q[i].d,&q[i].c); q[i].lx=1; } add(q[i].d); } sort(ls+1,ls+all+1); quchong(); chushi(); for (i=1;i<=m;i++) { if (q[i].lx==1) modify(q[i].d,q[i].c); if (q[i].lx==0) printf("%lld\n",getans(q[i].d)); } }}