Record My Thoughts
【题目大意】给定一个长度为N的没有相同元素的序列，然后让你求一个连续子串A[I],A[I+1]….A[J]使得A[I]是这短子串中的最小值，A[J]是这段子串中的最大值，并使得它J-I的值最大。
【算法分析】我先假设确定了起点，然后考虑在O(lgN)的复杂度里找到对应的最长长度。对于这个问题，我们可以考虑先找出以I为起点的区间范围，即以A[I]为最小值的区间范围。找出这个范围以后，只需要再找出其中的最大值所在的位置，就已经找出了以I为起点对应的最长区间了。（因为这个数在可取值的范围里最大，所以不能再延伸区间了）。对于实现这个算法，我们很容易得到确定了起点的最小值单调递减，于是我们可以二分得到这个范围，复杂度O(lgN)。然后那个取最大值和最小值均可以用RMQ在O(1)的复杂度内搞出来。由于预处理RMQ复杂度也为O(NlgN)，所以整个算法的复杂度是O(NlgN)。
【其它】1A，今天的第10题，刷完睡觉
6430690 edward2 2452 Accepted 12516K 766MS G++ 1971B 2010-02-10 01:08:32
【CODE】
#include
【题目大意】给定一个N*N的矩阵和M次染色，问最后是白色的格子还有多少个？
【算法分析】这题一看是线段树or矩形切割，但是仔细一想，可以发现一种新的算法，这中间利用了并差集。定义next[i,j]表示如果要染i，j这一个格子的话，应当去染哪一个格子。考虑我们写矩形切割的“浮冰法”，从后面开始进行insert，这样的话，后insert的必须避开先insert得。所以可以利用这个next进行跳跃。我这个next只针对当前行，就是next[i,j]的跳跃位置是对于第i行而言的。
初始时next[i,j]=j，表示要染这一格，那么就应该染这一格，比较拗口
然后如果对这一格被染色的话，那么next[i,j]=j+1，这样下一次就会越过我跳到下一格了，然后用并差集进行路径压缩，这样就能在平摊O(1)的复杂度调到下一个能染得格了！
这个算法中，对每个格子最多碰一次，所以染色的复杂度为O(N^2)，但是由于对于每一次染色，都必须枚举行，所以总复杂度是O(N^2+NM)。
【其它】1A,时限7S
997757 09.02.10 16:53 edward 177 .CPP Accepted 796 ms 9739 kb
【CODE】
#include
const int M=5555;
int n,m,next[N][N],x1[M],x2[M],y1[M],y2[M],color[N][N],dc[M];
void swap(int &x,int &y){
int tmp=x; x=y; y=tmp;
}
void init(){
for (int i=0;i<=n+1;i++)
for (int j=0;j<=n+1;j++)
next[i][j]=j;
}
int findnext(int i,int j){
if (next[i][j]==j) return j;
next[i][j]=findnext(i,next[i][j]);
return next[i][j];
}
void work(){
memset(color,200,sizeof(200));
for (int tmp=m;tmp>=0;tmp–)
for (int i=x1[tmp];i<=x2[tmp];i++){
for (int j=y1[tmp];j<=y2[tmp];)
if (next[i][j]==j){
color[i][j]=dc[tmp];
next[i][j]=j+1;
j++;
}
else j=findnext(i,j);
}
}
void print(){
int ans=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (color[i][j]==0) ans++;
printf("%dn",ans);
}
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d%d",&n,&m);
x1[0]=1; y1[0]=1; x2[0]=n; y2[0]=n;
for (int i=1;i<=m;i++){
int lx,ly,rx,ry;
char co;
scanf("%d%d%d%d %c",&lx,&ly,&rx,&ry,&co);
if (lx>rx) swap(lx,rx);
if (ly>ry) swap(ly,ry);
x1[i]=lx; x2[i]=rx; y1[i]=ly; y2[i]=ry;
if (co==’b’) dc[i]=1;
}
init();
work();
print();
return 0;
}
【题目大意】求每一段F[I]的最大值。
【算法分析】直接暴力打表。
【CODE】
#include
题意：
给定一棵无根树(边无向)，你一开始在s点上。
每次有两种操作。
1、0 x
表示走到x点上
2、1 i w
将第i条边的权值变为w
分析：
首先如果定义一个根，且d[i]为i点到根的距离。
那么必有dis(i,j)=d[i]+d[j]-2*d[lca(i,j)]
先按dfs顺序把点放进一个队列，这样如果以某点为根的子树的结点就会连续排列。
这样如果把某一条边改变以后，就相当如把以深度较大的那个点的为根的子树的所有d值都变为那个值。
那么这样的话就可以用线段树或者树状数组实现了。
插曲：
WA了很多遍，一开始work里很多东西写错，后来发现LCA写错。
cai0715-problem-solutions数据结构部分正式结束。
code：
#include
struct gtp{int x,y,w,next;}g[N];
int n,q,cur,ls[N],e,dep[N],d[N];
int Ql[N],Qt=0,pl[N],pr[N],El[N],Et=0,R[N],log2[N];
struct rmqtype{
int w[20][N],who[20][N];
void build(){
int maxk=log2[Et];
for (int i=1;i<=Et;i++) {
w[0][i]=dep[El[i]];
who[0][i]=El[i];
}
for (int k=1;k<=maxk;k++){
int t=1<
who[k][i]=who[k-1][i];
}
else{
w[k][i]=w[k-1][i+t];
who[k][i]=who[k-1][i+t];
}
}
}
int lca(int l,int r){
int t;
if (r
if (w[t][l]
}rmq;
struct Tree_Array_Type{
int a[N];
void clear(){memset(a,0,sizeof(a));}
void add(int pos,int x){
for (int i=pos;i<=n;i+=(i & -i)) a[i]+=x;
}
int sum(int pos){
int t=0;
for (int i=pos;i>=1;i-=(i & -i)) t+=a[i];
return t;
}
}Tarr;
void addedge(int x,int y,int w){
e++;
g[e].x=x; g[e].y=y; g[e].w=w; g[e].next=ls[x]; ls[x]=e;
}
void init(){
memset(ls,0,sizeof(ls));
memset(dep,0,sizeof(dep));
int pre=-1;
for (int i=1;i<=N;i++)
if ((1<<(pre+1))==i) log2[i]=++pre;
else log2[i]=pre;
scanf("%d%d%d",&n,&q,&cur);
for (int i=1;i<=n-1;i++){
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
addedge(x,y,w);
addedge(y,x,w);
}
}
void predfs(int p,int nowdep,int distance){
El[++Et]=p;
R[p]=Et;
Ql[++Qt]=p;
dep[p]=nowdep;
pl[p]=Qt;
d[p]=distance;
for (int t=ls[p];t>0;t=g[t].next)
if (dep[g[t].y]==0) {
predfs(g[t].y,nowdep+1,distance+g[t].w);
El[++Et]=p;
}
pr[p]=Qt;
}
void Build(){
Tarr.clear();
for (int i=1;i<=n;i++) {
Tarr.add(pl[i],d[i]);
Tarr.add(pl[i]+1,-d[i]);
}
rmq.build();
}
void work(){
int op,x,y;
for (int k=1;k<=q;k++){
scanf("%d",&op);
if (op==0){
scanf("%d",&x);
int fa=rmq.lca(R[cur],R[x]);
printf("%dn",Tarr.sum(pl[cur])+Tarr.sum(pl[x])-2*Tarr.sum(pl[fa]));
cur=x;
}
else{
scanf("%d%d",&x,&y);
int p=g[x*2].x;
if (dep[g[x*2].x]
Tarr.add(pl[p],change);
Tarr.add(pr[p]+1,-change);
g[x*2-1].w=y;
g[x*2].w=y;
}
}
}
int main(){
init();
predfs(1,1,0);
rmq.build();
Build();
work();
return 0;
}