放假回来状态回升？？（玩够了～但是稍困）
T1打的不完全对，但是过掉了。很快的想到了二分吧喇叭啦。。
然后T2也挺快想出来了但是挂细节没发现，考试快结束的时候才发现出锅了。
改了过来是正解，但是出题人无良卡了线段树强制树状数组，T了一个子任务，卡常到飞起。
T3暴力没什么问题。
卡常是一种习惯。要注意题目数据范围观察是否卡常。
T1：
所有的决策都是一条一次函数。
分两类，斜率正或斜率非负。
如果第二类的直线里有在T=0时符合要求的，那么答案就是0，所以check(0)一下。
如果非负的直线都在T=0时不符合要求，那么以后这些直线都不符合要求了。
所以排除，只剩下斜率为正的直线了，它们到底什么时候符合要求？
因为斜率都是正的，那么现在符合要求以后也一定符合，满足单调性。
二分。贪心。nth_element（sort被卡复杂度）。
注意判断价值为负的物品不选，而不是一定选满m个。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 #define int long long 5 int n,m,S,k[1000005],b[1000005],res[1000005]; 6 bool chk(int tim){int tot=0;//printf("%lld ",tim); 7 for(int i=1;i<=n;++i)res[i]=k[i]*tim+b[i]; 8 nth_element(res+1,res+n-m+1,res+n+1); 9 for(int i=n-m+1;i<=n;++i)if(res[i]>=0){tot+=res[i];if(tot>=S)return true;}//printf("%lld %lld\n",tot,S); 10 return tot>=S; 11 } 12 main(){//freopen("merchant3.in","r",stdin); 13 scanf("%lld%lld%lld",&n,&m,&S);//printf("%lld %lld\n",n,m); 14 for(int i=1;i<=n;++i)scanf("%lld%lld",&k[i],&b[i]); 15 int l=0,r=1000000000; 16 while(l<r-1)if(chk(l+r>>1))r=l+r>>1;else l=(l+r>>1)+1; 17 printf("%lld\n",chk(l)?l:r); 18 }
同理可证总决策线是个单谷函数。
思路积累：
- 分类讨论：直线斜率的正负。
T2：
因为是一棵树，设根的权值为x，那么每个点的权值都可以根据路径上的方程来表示为含x的式子：x+a或a-x。a是常数
然后对于询问，分类讨论解方程即可。
对于修改，子树内的点的表达式都有变化。
可以发现，深度为奇数的点都是加，偶数的点都是减。
第一想法是线段树，直接子树加，在叶节点特殊处理加减即可。
1 #include<cstdio> 2 int n,q,dep[1000005],f[1000005],w[1000005],W[1000005],tim,re[1000005]; 3 int fir[1000005],l[1000005],to[1000005],cnt,dfn[1000005],rdfn[1000005]; 4 void link(int a,int b){l[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;} 5 void dfs(int p){ 6 dep[p]=dep[f[p]]+1;w[p]=W[p]-w[f[p]];dfn[p]=++tim;re[tim]=p; 7 for(int i=fir[p];i;i=l[i])dfs(to[i]);rdfn[p]=tim; 8 } 9 struct Segment_Tree{ 10 int cl[4000005],cr[4000005],tw[4000005],lz[4000005]; 11 void build(int l,int r,int p=1){ 12 cl[p]=l;cr[p]=r; 13 if(l==r){tw[p]=w[re[l]];return;} 14 build(l,l+r>>1,p<<1);build((l+r>>1)+1,r,p<<1|1); 15 } 16 void down(int p){ 17 tw[p<<1]+=lz[p]*((dep[re[cl[p<<1]]]&1)?1:-1); 18 tw[p<<1|1]+=lz[p]*((dep[re[cl[p<<1|1]]]&1)?1:-1);//printf("down:%d %d\n",re[cl[p<<1]],re[cr[p<<1|1]]); 19 lz[p<<1]+=lz[p];lz[p<<1|1]+=lz[p]; 20 lz[p]=0; 21 } 22 void add(int l,int r,int _w,int p=1){//printf("add:%d %d %d\n",p,cl[p],cr[p]); 23 if(l<=cl[p]&&cr[p]<=r){lz[p]+=_w;tw[p]+=_w*((dep[re[cl[p]]]&1)?1:-1);return;} 24 if(lz[p])down(p); 25 if(l<=cr[p<<1])add(l,r,_w,p<<1); 26 if(r>=cl[p<<1|1])add(l,r,_w,p<<1|1); 27 } 28 int ask(int pos,int p=1){ 29 if(cl[p]==cr[p])return tw[p]; 30 if(lz[p])down(p); 31 return pos<=cr[p<<1]?ask(pos,p<<1):ask(pos,p<<1|1); 32 } 33 }T; 34 int main(){ 35 scanf("%d%d",&n,&q); 36 for(int i=2;i<=n;++i)scanf("%d%d",&f[i],&W[i]),link(f[i],i); 37 dfs(1);T.build(1,n);//for(int i=1;i<=n;++i)printf("%d ",w[i]); 38 for(int i=1,opt,u,v,ww;i<=q;++i){ 39 scanf("%d",&opt); 40 if(opt==1){ 41 scanf("%d%d%d",&u,&v,&ww);int Q=T.ask(dfn[u])+T.ask(dfn[v]);//printf("%d %d\n",T.ask(dfn[u]),T.ask(dfn[v])); 42 if(dep[u]&1^dep[v]&1)puts(Q==ww?"inf":"none"); 43 else if(Q-ww&1)puts("none"); 44 else if(dep[u]&1)printf("%d\n",ww-Q>>1); 45 else printf("%d\n",Q-ww>>1); 46 }else scanf("%d%d",&u,&ww),T.add(dfn[u],rdfn[u],(ww-W[u])*((dep[u]&1)?1:-1)),W[u]=ww; 47 } 48 }
那么考虑如何用树状数组来维护。
区间加，单点查询。树状数组不能直接做，所以要差分。
根据度数奇偶加减不同，那么如果我们把度数为奇数的点都取相反数。
取出来的时候再相反数一下就好了。
1 #include<cstdio> 2 #define int long long 3 int dep[1000005],f[1000005],w[1000005],W[1000005],tim,re[1000005],n; 4 int fir[1000005],l[1000005],to[1000005],cnt,dfn[1000005],rdfn[1000005]; 5 inline void link( int a, int b){l[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;} 6 const int L=1<<20|1; 7 char buffer[L],*S,*TT; 8 #define getchar() ((S==TT&&(TT=(S=buffer)+fread(buffer,1,L,stdin),S==TT))?EOF:*S++) 9 const int maxn=100000+5; 10 inline int read(register int &p,register int nt=1,register char ch=getchar()){p=0; 11 while(ch>'9'||ch<'0'){if(ch=='-')nt=-1;ch=getchar();} 12 while(ch<='9'&&ch>='0')p=(p<<3)+(p<<1)+ch-48,ch=getchar();p*=nt; 13 } 14 void dfs(int p){ 15 dep[p]=dep[f[p]]^1;w[p]=W[p]-w[f[p]];dfn[p]=++tim;re[tim]=p; 16 for(int i=fir[p];i;i=l[i])dfs(to[i]);rdfn[p]=tim; 17 } 18 struct Tree_Array{ 19 int t[1000005]; 20 inline void ADD(int p,int w){for(;p<=1000000;p+=p&-p)t[p]+=w;} 21 inline int SUM(int p,int a=0){for(;p;p^=p&-p)a+=t[p];return a;} 22 inline void add(int L,int R,int w){ADD(L,w);ADD(R+1,-w);} 23 inline int ask(int p){return SUM(p)*(dep[re[p]]?1:-1);} 24 inline void build(){for(int i=1;i<=n;++i)ADD(i,(w[re[i]]*(dep[re[i]]?1:-1))-(w[re[i-1]]*(dep[re[i-1]]?1:-1)));} 25 }T; 26 main(){ 27 int q;scanf("%d%d",&n,&q); 28 for(int i=2;i<=n;++i)read(f[i]),read(W[i]),link(f[i],i); 29 dfs(1);T.build(); 30 for(int i=1,opt,u,v,ww;i<=q;++i){ 31 read(opt); 32 if(opt==1){ 33 read(u);read(v);read(ww); int Q=T.ask(dfn[u])+T.ask(dfn[v]); 34 if(dep[u]^dep[v])puts(Q==ww?"inf":"none"); 35 else if(Q-ww&1)puts("none"); 36 else if(dep[u])printf("%d\n",ww-Q>>1); 37 else printf("%d\n",Q-ww>>1); 38 }else read(u),read(ww),T.add(dfn[u],rdfn[u],(ww-W[u])*(dep[u]?1:-1)),W[u]=ww; 39 } 40 }
思路积累：
- 树状数组维护特殊操作：存相反数
T3：
还在改。咕。。。
其实不是不会写而咕。
但是第二机房实在是太颓了。。。效率超低。。。
一下午基本什么都没干。。
再不回去我可能就要毁了。。。
但是看现在这个总分好像还是很悬啊。。。
我想回去。。。