bzoj1036题解
2024-10-07 20:38:05
【解题思路】
直接上树剖套线段树/BIT即可。复杂度o(n+qlog22n)（线段树）或o(n+qlog23n)（BIT）。
【参考代码】
树剖套BIT。（这个树剖好naive啊QAQ）
#include <algorithm>
#include <cctype>
#include <cstdio>
#define REP(I,start,end) for(int I=(start);I<=(end);I++)
#define PER(I,start,end) for(int I=(start);I>=(end);I--)
#define ClearStack(_stack) while(!_stack.empty()){_stack.pop();}
#define ClearQueue(_queue) while(!_queue.empty()){_queue.pop();}
#define ClearArray(_array,from,to,val) REP(i,from,to){_array[i]=val;}
#define maxint 32767
#define maxlongint 2147483647
#define maxint64 9223372036854775807ll
inline void space()
{
putchar(' ');
}
inline void enter()
{
putchar('\n');
}
inline bool eoln(char ptr)
{
return ptr=='\n';
}
inline bool eof(char ptr)
{
return ptr=='\0';
}
inline int getint()
{
char ch=getchar();
for(;!isdigit(ch)&&ch!='+'&&ch!='-';ch=getchar());
bool impositive=ch=='-';
if(impositive)
ch=getchar();
int result=;
for(;isdigit(ch);ch=getchar())
result=(result<<)+(result<<)+ch-'';
return impositive?-result:result;
}
inline char *getstr()
{
char *result=new char[],*ptr=result,ch=getchar();
for(;isspace(ch)||eoln(ch)||eof(ch);ch=getchar());
for(;!isspace(ch)&&!eoln(ch)&&!eof(ch);ch=getchar())
{
*ptr=ch;
ptr++;
}
*ptr='\0';
return result;
}
template<typename integer> inline int write(integer n)
{
integer now=n;
bool impositive=now<;
if(impositive)
{
putchar('-');
now=-now;
}
char sav[];
sav[]=now%+'';
int result=;
for(;now/=;sav[result++]=now%+'');
PER(i,result-,)
putchar(sav[i]);
return result+impositive;
}
template<typename T> inline bool getmax(T &target,T pattern)
{
return pattern>target?target=pattern,true:false;
}
template<typename T> inline bool getmin(T &target,T pattern)
{
return pattern<target?target=pattern,true:false;
}
template<typename T> class BIT
{
private:
int size;
T _nINF,_INF,*sav,*savSum,*savMax,*savMin;
int lowbit(int now)
{
return now&-now;
}
public:
inline void clear(int length,T nINF=-maxlongint,T INF=maxlongint)
{
size=length;
delete []sav;
delete []savSum;
delete []savMax;
delete []savMin;
sav=new T[size+];
savSum=new T[size+];
savMin=new T[size+];
savMax=new T[size+];
_nINF=nINF;
_INF=INF;
ClearArray(sav,,size,);
ClearArray(savSum,,size,);
ClearArray(savMax,,size,_nINF);
ClearArray(savMin,,size,_INF);
}
inline void increase(int point,T delta)
{
sav[point]+=delta;
for(int i=point;i<=size;i+=lowbit(i))
{
savSum[i]+=delta;
savMax[i]=savMin[i]=sav[i];
for(int j=;j<lowbit(i);j<<=)
{
getmax(savMax[i],savMax[i-j]);
getmin(savMin[i],savMin[i-j]);
}
}
}
inline void change(int point,T val)
{
T delta=val-sav[point];
sav[point]=val;
for(int i=point;i<=size;i+=lowbit(i))
{
savSum[i]+=delta;
savMax[i]=savMin[i]=sav[i];
for(int j=;j<lowbit(i);j<<=)
{
getmax(savMax[i],savMax[i-j]);
getmin(savMin[i],savMin[i-j]);
}
}
}
inline T pre_sum(int length)
{
T result=T();
for(int i=length;i;i-=lowbit(i))
result+=savSum[i];
return result;
}
inline T query_sum(int left,int right)
{
return pre_sum(right)-pre_sum(left-);
}
inline T query_max(int left,int right)
{
T result=sav[right];
for(int l=left,r=right;l<r;)
{
for(r--;r-l>=lowbit(r);r-=lowbit(r))
getmax(result,savMax[r]);
getmax(result,sav[r]);
}
return result;
}
inline T query_min(int left,int right)
{
T result=sav[right];
for(int l=left,r=right;l<r;)
{
for(r--;r-l>=lowbit(r);r-=lowbit(r))
getmin(result,savMin[r]);
getmin(result,sav[r]);
}
return result;
}
};
//=============================Header Template===============================
#include <cstring>
#include <vector>
using namespace std;
typedef vector<int> vecint;
BIT<int> bit[];
int depth[],w[],father[],weight[],wfa[],wson[],group[],position[];
vecint lines[];
int DFS(int now)
{
weight[now]=;
for(vecint::iterator i=lines[now].begin();i!=lines[now].end();i++)
{
int p=*i;
if(!weight[p])
{
father[p]=now;
weight[now]+=DFS(p);
}
}
return weight[now];
}
void DFSdep(int now,int deep)
{
if(!now)
return;
depth[now]=deep;
for(vecint::iterator i=lines[now].begin();i!=lines[now].end();i++)
{
int p=*i;
if(p!=father[now]&&p!=wson[now])
DFSdep(p,deep+);
}
DFSdep(wson[now],deep);
}
int main()
{
int n=getint();
memset(lines,,sizeof(lines));
REP(i,,n)
{
int u=getint(),v=getint();
lines[u].push_back(v);
lines[v].push_back(u);
}
REP(i,,n)
w[i]=getint();
memset(weight,,sizeof(weight));
father[]=father[]=;
DFS();
memset(wson,,sizeof(wson));
REP(i,,n)
{
int maxer=;
for(vecint::iterator j=lines[i].begin();j!=lines[i].end();j++)
{
int p=*j;
if(p!=father[i]&&getmax(maxer,weight[p]))
wson[i]=p;
}
}
int cnt=;
DFSdep(,);
REP(i,,n)
if(wson[father[i]]!=i)
{
cnt++;
int place=;
for(int j=i;j;j=wson[j])
{
wfa[j]=i;
group[j]=cnt;
position[j]=++place;
}
bit[cnt].clear(place);
for(int j=i;j;j=wson[j])
bit[cnt].change(position[j],w[j]);
}
int q=getint();
while(q--)
{
char *opt=getstr();
int u=getint(),v=getint();
if(!strcmp(opt,"CHANGE"))
bit[group[u]].change(position[u],v);
if(!strcmp(opt,"QSUM"))
{
int ans=;
for(;depth[u]>depth[v];u=father[wfa[u]])
{
int left=position[u],right=position[wfa[u]];
if(left>right)
swap(left,right);
ans+=bit[group[u]].query_sum(left,right);
}
for(;depth[u]<depth[v];v=father[wfa[v]])
{
int left=position[v],right=position[wfa[v]];
if(left>right)
swap(left,right);
ans+=bit[group[v]].query_sum(left,right);
}
for(;wfa[u]!=wfa[v];u=father[wfa[u]],v=father[wfa[v]])
{
int left=position[u],right=position[wfa[u]];
if(left>right)
swap(left,right);
ans+=bit[group[u]].query_sum(left,right);
left=position[v];right=position[wfa[v]];
if(left>right)
swap(left,right);
ans+=bit[group[v]].query_sum(left,right);
}
int left=position[u],right=position[v];
if(left>right)
swap(left,right);
ans+=bit[group[u]].query_sum(left,right);
write(ans);
enter();
}
if(!strcmp(opt,"QMAX"))
{
int ans=-maxlongint;
for(;depth[u]>depth[v];u=father[wfa[u]])
{
int left=position[u],right=position[wfa[u]];
if(left>right)
swap(left,right);
getmax(ans,bit[group[u]].query_max(left,right));
}
for(;depth[u]<depth[v];v=father[wfa[v]])
{
int left=position[v],right=position[wfa[v]];
if(left>right)
swap(left,right);
getmax(ans,bit[group[v]].query_max(left,right));
}
for(;wfa[u]!=wfa[v];u=father[wfa[u]],v=father[wfa[v]])
{
int left=position[u],right=position[wfa[u]];
if(left>right)
swap(left,right);
getmax(ans,bit[group[u]].query_max(left,right));
left=position[v];right=position[wfa[v]];
if(left>right)
swap(left,right);
getmax(ans,bit[group[v]].query_max(left,right));
}
int left=position[u],right=position[v];
if(left>right)
swap(left,right);
getmax(ans,bit[group[u]].query_max(left,right));
write(ans);
enter();
}
}
return ;
}
最新文章
- [源码]String StringBuffer StringBudlider（2）StringBuffer StringBuilder源码分析
- [转]保护眼睛的Windows和IE、Firefox、谷歌等浏览器颜色设置
- Python学习（基础简绍）
- PHP面向对象05_接口与多态
- Ring3无敌进程让你的进程变得和smss.exe一样支持64
- Robots on a grid（DP+bfs()）
- 在CentOS下企图整合Apache和Tomcat依然失败
- ASCII码表详解
- 352. Data Stream as Disjoint Intervals
- TIMESTAMP和DATETIME的区别
- ImageNet && 医学图像的识别
- 揭开枚举类的面纱（Unlocking the Enumeration/enum Mystery）
- Linux下使用javac编译
- 题解 P4753 【River Jumping】
- android面试题总结加强再加强版（一）
- 关于${pageContext.request.contextPath}的理解 （转载）
- Windows平台搭建Kafka
- HBase scan setBatch和setCaching的区别
- Flask web开发之路十二
- Python网络爬虫第一弹《Python网络爬虫相关基础概念》