五:扩张多语言版本首页,不一样的言语下:依照小说所选归选语言类别排序该品种语言小说在后边

Description

给定壹棵有n个节点的无根树和m个操作,操作有二类:

1、将节点a到节点b路径上全部点都染成颜色c;

二、询问节点a到节点b路径上的颜色段数量(一连相同颜色被认为是均等段),如“1122二一”由三段组成:“1一”、“22贰”和“①”。

请您写一个程序依次实现那m个操作。

 

统计 1统计 2

Output

对于各样询问操作,输出壹行答案。

5:48小时[点击/评论]排行/最新评论:同主界面列表,根据小说的语言归类排序。

Sample Input

6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5

一:扩大系统一分配类,允许用户公布作品到首页。

Input

首先行李包裹蕴三个整数n和m,分别代表节点数和操作数;

其次行包涵n个正整数表示n个节点的起来颜色

下边 行每行李包裹涵多少个整数x和y,表示xy里面有一条无向边。

下边 行每行描述3个操作:

“C a b
c”表示这是3个染色操作,把节点a到节点b路径上全数点(包蕴a和b)都染成颜色c;

“Q a
b”表示那是三个精通操作,询问节点a到节点b(包蕴a和b)路径上的颜料段数量。

首页的多语言主要表今后:

2017年10月20日

贰:扩展积分排行,于是原V一.0并未有积分总括效率,那里补上了。

Sample Output

3
1
2

从而,此番V二.0的文告,新扩展了两套皮肤,1套从微博的专业皮肤借来,另1套从小泥鳅博客的首页借来,希望能创新下大伙的视觉效果。

HINT

数N<=10^5,操作数M<=10^伍,全体的颜色C为整数且在[0, 10^9]之间。、

 

题解:

标题很好了然,它不是边染色,而是点染色,那些特性是比较好的,边染色还须要裂点。

看的标题就能够想到那是树链剖分模板题吗,套个裸的线条树合并,其实未有怎么统一的

东西,发现1段线段的分裂颜色,那么就要求记录左端点和右端点颜色,假诺左区间右端

点和右区间左端颜色相同,那么总颜色-1,那一个比较好了然的呢,然后记录2个该距离总

颜色数,就足以计算了。

程序比较结构化
三个dfs预处理,lca,线段树,询问处理+更新处理,就ok了,代码比较清晰。

  1 #include<cstring>
  2 #include<cmath>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<cstdio>
  6 #include<cstdlib>
  7 #define N 100007
  8 using namespace std;
  9 
 10 int n,m,sz=0;
 11 int cnt,head[N],next[N*2],rea[N*2];
 12 int a[N];
 13 int fa[N][20],size[N],pos[N],bel[N],deep[N];
 14 char ch[2];
 15 struct Node
 16 {
 17     int lc,rc,tag,num;
 18 }tr[N*5];
 19 
 20 void add(int u,int v){next[++cnt]=head[u],head[u]=cnt,rea[cnt]=v;}
 21 void dfs_init(int u)
 22 {
 23     size[u]=1;
 24     for (int i=1;(1<<i)<=deep[u];i++)
 25         fa[u][i]=fa[fa[u][i-1]][i-1];
 26     for (int i=head[u];i!=-1;i=next[i])
 27     {
 28         int v=rea[i];
 29         if (v==fa[u][0]) continue;
 30         deep[v]=deep[u]+1;
 31         fa[v][0]=u;
 32         dfs_init(v);
 33         size[u]+=size[v];
 34     }
 35 }
 36 void dfs_make(int u,int chain)
 37 {
 38     int k=0;
 39     pos[u]=++sz,bel[u]=chain;
 40     for (int i=head[u];i!=-1;i=next[i])
 41     {
 42         int v=rea[i];
 43         if (deep[v]>deep[u]&&size[v]>size[k]) k=v;
 44     }
 45     if (k==0) return;
 46     dfs_make(k,chain);
 47     for (int i=head[u];i!=-1;i=next[i])
 48     {
 49         int v=rea[i];
 50         if (deep[v]>deep[u]&&v!=k) dfs_make(v,v);
 51     }
 52 }
 53 int lca(int a,int b)
 54 {
 55     if (deep[a]<deep[b]) swap(a,b);
 56     int i;
 57     for (i=0;(1<<i)<=deep[a];i++);
 58     i--;
 59     for (int j=i;j>=0;j--)
 60         if (deep[a]-(1<<j)>=deep[b]) a=fa[a][j];
 61     if (a==b) return a;
 62     for (int j=i;j>=0;j--)
 63         if (fa[a][j]!=fa[b][j]) a=fa[a][j],b=fa[b][j];
 64     return fa[a][0];        
 65 }
 66 void updata_down(int l,int r,int p)
 67 {
 68     int tag=tr[p].tag;tr[p].tag=-1;
 69     if (tag==-1||l==r) return;
 70     tr[p<<1].num=tr[p<<1|1].num=1;
 71     tr[p<<1].tag=tr[p<<1|1].tag=tag;
 72     tr[p<<1].lc=tr[p<<1].rc=tag;
 73     tr[p<<1|1].lc=tr[p<<1|1].rc=tag;
 74 }
 75 void updata_up(int l,int r,int p)
 76 {
 77     tr[p].lc=tr[p<<1].lc,tr[p].rc=tr[p<<1|1].rc;
 78     tr[p].num=tr[p<<1].num+tr[p<<1|1].num;
 79     if (tr[p<<1].rc==tr[p<<1|1].lc) tr[p].num--;
 80 }
 81 void change(int l,int r,int p,int x,int y,int z)
 82 {
 83     updata_down(l,r,p);
 84     if (l==x&&y==r)
 85     {tr[p].num=1,tr[p].lc=tr[p].rc=tr[p].tag=z;return;}
 86     int mid=(l+r)>>1;
 87     if (y<=mid) change(l,mid,p<<1,x,y,z);
 88     else if (x>mid) change(mid+1,r,p<<1|1,x,y,z);
 89     else change(l,mid,p<<1,x,mid,z),change(mid+1,r,p<<1|1,mid+1,y,z);
 90     updata_up(l,r,p);
 91 }
 92 int query(int l,int r,int p,int x,int y)
 93 {
 94     updata_down(l,r,p);
 95     if (l==x&&y==r) return tr[p].num;
 96     int mid=(l+r)>>1,res;
 97     if (y<=mid) res=query(l,mid,p<<1,x,y);
 98     else if (x>mid) res=query(mid+1,r,p<<1|1,x,y);
 99     else
100     {
101         res=query(l,mid,p<<1,x,mid)+query(mid+1,r,p<<1|1,mid+1,y);
102         if (tr[p<<1].rc==tr[p<<1|1].lc) res--;
103     }
104     return res;
105 }
106 int find(int l,int r,int p,int x)
107 {
108     updata_down(l,r,p);
109     if (l==r) return tr[p].lc;
110     int mid=(l+r)>>1;
111     if (x<=mid) return find(l,mid,p<<1,x);
112     else return find(mid+1,r,p<<1|1,x);
113 }
114 int solvequery(int x,int fq)
115 {
116     int res=0;
117     while(bel[x]!=bel[fq])
118     {
119         res+=query(1,n,1,pos[bel[x]],pos[x]);
120         if (find(1,n,1,pos[bel[x]])==find(1,n,1,pos[fa[bel[x]][0]])) res--;
121         x=fa[bel[x]][0];
122     }
123     res+=query(1,n,1,pos[fq],pos[x]);
124     return res;
125 }
126 void solvechange(int x,int fq,int z)
127 {
128     while(bel[x]!=bel[fq])
129     {
130         change(1,n,1,pos[bel[x]],pos[x],z);
131         x=fa[bel[x]][0];
132     }
133     change(1,n,1,pos[fq],pos[x],z);
134 }
135 int main()
136 {
137     memset(head,-1,sizeof(head));tr[1].tag=-1;
138     scanf("%d%d",&n,&m);
139     for(int i=1;i<=n;i++)
140         scanf("%d",&a[i]);
141     int x,y,z;
142     for (int i=1;i<n;i++)
143     {
144         scanf("%d%d",&x,&y);
145         add(x,y),add(y,x);
146     }
147     dfs_init(1);
148     dfs_make(1,1);
149     for (int i=1;i<=n;i++)
150         change(1,n,1,pos[i],pos[i],a[i]);            
151 //==============================================================
152     for (int i=1;i<=m;i++)
153     {
154         scanf("%s",ch);
155         if (ch[0]=='Q')
156         {
157             scanf("%d%d",&x,&y);
158             int par=lca(x,y);
159             printf("%d\n",solvequery(x,par)+solvequery(y,par)-1); 
160         }
161         else
162         {
163             scanf("%d%d%d",&x,&y,&z);
164             int par=lca(x,y);
165             solvechange(x,par,z),solvechange(y,par,z);
166         }
167     }
168 }

 

3:2010年11月15日—匡助多语言、多用户、多数据库、目录级U奥迪Q5L之路过上秋版博客
V壹.0正式版
发布[含详细计划安装表明]

 

所以,此次V贰.0版本的发布,将制止那种景观,直接设置好有关的权限,真正做到壹键解决。

1:从新浪首页借了点html+css,多语言作用增强[截图在终极面]

5:开放多国语言在线编辑,允许网页编辑多国语言

 

 

 

1:后台扩张语言设置,设置之后,被网上朋友浏览时[切换语言时],系统一分配类和作品列表将按文章语言翻译及排序,未安装语言时则不按文章语言排序及翻译。

本V2.0版本[暂定为测试版本],将拓展公测17日,欢迎大家继续测试:网站:http://www.cyqdata.com/

2:用户多语言

统计 3

以致从外在直接影响对整系统的视角,觉的不标准或太简陋,出现此原因是出于个体不要正规美术工作,说白点就是不懂美工,

叁:修改原来的系统首页,抓好首页彰显效果

25日内若有Bug发现将勘误重新发表正式版,若无,将不再发表版本。

二:增加了2套皮肤

6:缓存:对多少个语言版本举行缓存,用户切换语言时见到的是见仁见智的多寡。

统计 4统计 5

1:2010年11月08日—支持多语言、多用户、多数据库、目录级URL之路过早秋版博客发表[相对有杀伤力的博客]

 

V一.0本子的揭破,尽管作用强大,但其简洁的原本皮肤,并不入部分网络朋友的法眼,加上网民对系统皮肤成效的不打听,

网络好友也不驾驭是那种原因所致,因故导致大多数网络朋友对V壹.0版本兴趣缩短。

本子升级至关心珍视要内容:

末段:系统公测地址:秋色园

随着首页的改版,系统功用也加剧了变动了,犹其是在多语言版本效果上,首要作用有:

壹:从天涯论坛和小泥鳅博客里借来了两套皮肤

三:首页多语言 说明:

1人翻译多国语言太辛勤了,直接开放,集网民众力量量,每人编辑多少个,刷刷刷就做到了。
方今选拔另和备份方式开放编辑,由此扩展了“预览”成效。

V一.0的Access数据库暗许放在根目录,暗中认可对其尚无设置写权限,因而导致网民在下载后运转时,

 

二:网址分类多语言:分类唯有两种语言,即系统设定默许语言为主语言[显示分类的Name],别的的言语都显得另1种名称[展现分类的PKey]

四:多语言应用抓牢[首页/用户/文章]

 

2:2010年11月10日—基本功却简单被忽视的那一点事–web侵犯方式及注意事项总计

 

说明:

4:2010年11月17日—途经首秋版博客-皮肤制作指南
[附犀利哥入侵进攻和防守站话题]

所以无法制作出美丽的皮肤,为系统穿上美丽的衣衫。

1:”路过白藏版博客一键安装工具.exe”升级,扩展私下认可对Access数据库的写权限。

 

 

接下去是V2.0 发布正文
[
系统公测地址:[秋色园](http://www.cyqdata.com/)\]

下载地址:CYQ.Data 轻量数据层之路
bug反馈、优化建议、最新框架下载

1:粤语版系统首页:

统计 6

5:开放多国语言在线编辑,允许网页编辑多国语言

此间补上几张截图:

 

说明:

四:多语言使用狠抓[文章/用户/首页**]**

 

不得不浏览,却无力回天进展“注册/提交文章”等富含写数据库数据的操作,加上操作提醒的不明显,

统计 7

一:将私下认可Access数据库移到App_Data目录,并对其安装可写权限

四:主界面小说列表:依照小说的语言归类进行排序,因而,在差异的言语切换时,保险首页为新型的该语言文章在前边。

说明:

三:修改系统主页,借了部分新浪的首页html和css

行经高商版博客发表历史回想:

四:扩展首页列表呈现:首页作品、4八钟头点击排行、4捌小时评论排行、最新评论等效果。

细微预览:

说明:

 

3个便于被遗漏的链接[在线多国语言编辑]: http://www.cyqdata.com/lang/edit

二:E文版系统首页:

 

三:系统积分排名:只呈现二种语言:即系统设定私下认可语言为主语言[来得用户的外号],别的的言语都展现另一种名称[呈现用户的用户名]

 

小说的多语言首要呈今后:

下边进行重大描述表达:

 

 

1:系统多语言成效:对界面进行多语言翻译

1:小说扩展“语言归类”,分裂的言语归类会在用户首页和系统首页彰显不一致。

说明:

 

一:将多国语言文件开放在web上让用户编辑

壹:“路过上秋版博客一键安装工具.exe”升级

一:作品多语言

叁:增添系统总计:用户、小说、相片、文章评价、相片评论。

 

 

说明:

用户的多语言首要呈未来:

2:增加2套皮肤