算法整理（四）

文章目录

9.数据结构

9.数据结构

9.1 队列

9.1.1 单调队列

有一个长为 n 的序列，以及一个大小为 k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
单调队列与普通队列不一样的地方就在于单调队列既可以从队首出队，也可以从队尾出队。用deque。

#include 
using namespace std;
struct Node
{
	int v,pos;
}node[1000050];
deque<Node>q;
int n,k;

int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&node[i].v);
		node[i].pos=i;
	}
	for(int i=1;i<=n;i++)
	{
		while(q.size()&&node[i].v<q.back().v)
		 	q.pop_back();//从后端弹出不优的结点（不优：下标小，数值还大） 
		q.push_back(node[i]);
		while(q.size()&&q.front().pos<i-k+1)
			q.pop_front();//从前端弹出窗口范围外的节点 
		if(i>=k) printf("%d ",q.front().v);
	}
	cout<<endl;
	q.clear();
	for(int i=1;i<=n;i++)
	{
		while(q.size()&&node[i].v>q.back().v)
		 	q.pop_back();
		q.push_back(node[i]);
		while(q.size()&&q.front().pos<i-k+1)
			q.pop_front();
		if(i>=k) printf("%d ",q.front().v);
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

9.2 栈

9.2.1 单调栈

快速获得每个数之后一个比它大（小）的元素，时间复杂度为O ( n )

#include 
using namespace std;
const int N=3000050;
int ans[N],a[N],st[N];
//a:数据数组
//st:模拟栈（储存的是数值的对应下标）（单调递减栈） 
//ans:储存每个下标对应的答案 
int n,k=0;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		while(a[i]>a[st[k]]&&k)
			ans[st[k--]]=i;//取走栈内比当前元素大的元素，并且更新这些被取走元素的答案 
		st[++k]=i;//将当前元素放入栈内 
	}
	for(int i=1;i<=n;i++)
		printf("%d ",ans[i]) ;
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

9.3 链表

特殊约瑟夫问题(链表)：
编号为1…N的N个小朋友玩游戏，他们按编号顺时针围成一圈，从第一个人开始按逆时针次序报数，报到第M个人出列；然后再从下个人开始按顺时针次序报数，报到第K个人出列；再从下一个人开始按逆时针次序报数，报到第M个人出列；再从下个人开始按顺时针次序报数，报到第K个人出列……以此类推不断循环，直至最后一人出列。请编写程序按顺序输出出列人的编号。

#include  
using namespace std;  
typedef struct tagNode  
{  
    int data;  
    struct tagNode *pre,*next;  
}Node,*LinkList;  
  
void InitList(LinkList *L)  
{  
    *L=(LinkList)malloc(sizeof(Node));  
    //获取Node的字段长度，然后强转为LinkList类型。L变量就代表地址长
度和Node一样所占内存空间同样大小的LinkList  
    (*L)->next=(*L)->pre=*L;  
    //初始化：两个指针都指向自身   
}  
  
int main()  
{  
    int n,m,k,i;  
    cin>>n>>m>>k;  
    LinkList L;  
    InitList(&L);  
    struct tagNode *p,*q,*g;  
    p=(LinkList)malloc(sizeof(Node));  
    g=q=p;  
    p->data=1;  
    p->next=p;  
    for(i=2;i<=n;i++)  
    {  
        q = (q->next=(LinkList)malloc(sizeof(Node)));  
        q->pre=g;  
        q->data=i;  
        q->next=p;  
        g=g->next;  
    }  
    p->pre=g;  
    q=p;  
    for(int cnt=1;cnt<=n;cnt++)  
    {  
        if(cnt&1)  
        {  
            if (m == 1)  
            {  
                printf("%d", q->data);  
                q->next->pre = q->pre;  
                q->pre->next = q->next;  
               q = q->pre;  
            }  
            else  
            {  
                for (i=2;i<m;i++)  
                    q=q->pre;  
                printf("%d ",q->pre->data);  
                q->pre=q->pre->pre;  
                q->pre->next=q;  
                q = q->pre;  
            }  
        }  
        else  
        {  
            if (k == 1)  
            {  
                printf("%d", q->data);  
                q->next->pre=q->pre;  
                q->pre->next=q->next;  
                q = q->next;  
            }  
            else  
            {  
                for (i=2;i<k; i++)  
                    q=q->next;  
                printf("%d ", q->next->data);  
                q->next=q->next->next; 
                q->next->pre=q;  
                q=q->next;  
            }  
        }  
    }  
    return 0;  
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

9.4 树

9.4.1 二叉树

二叉树叶结点值和最大层
已知一棵非空二叉树结点的数据域为不等于0的整数，请编写程序找出该二叉树中叶结点数据值之和最大的层。

#include
using namespace std;

int sum[101],total,depth=1;

typedef struct Binary_tree_node
{
	int data;
	struct Binary_tree_node *left_leave,*right_leave;
}Binary_tree_node,*Link;

Link create()
{
	int num;
	Link node;
	cin>>num;
	if(!num)
		node=NULL;
	else
	{
		node=(Link)malloc(sizeof(Binary_tree_node));
		node->data=num;
		node->left_leave=create();
		node->right_leave=create();
	}
	return node;
}

void fuc(Link BT)
{
	if(BT)
	{
		if(BT->left_leave==NULL&&BT->right_leave==NULL)
			sum[depth]+=BT->data;
		fuc(BT->left_leave);
		fuc(BT->right_leave);
		if(BT->left_leave!=NULL&&BT->right_leave!=NULL)
			depth++;
	}
	return;
}

int cmp(int *arr,int depth)
{
	int i,temp=arr[0],index=0;
	for(i=1;i<depth;i++)
	{
		if(arr[i]>=temp)
		{
			temp=arr[i];
			index=i;
		}
	}
	return index;
}
int main()
{
	Link tree=NULL;
	tree=create();
	fuc(tree);
	int ans=cmp(sum,depth);
	cout<<ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

前序和中序构造二叉树
本题目要求用先序序列和中序序列构造一棵二叉树（树中结点个数不超过10个），并输出其后序序列。

#include
using namespace std;
int n;
int front[11],mid[11];
void fun(int ll,int lr,int rl,int rr)
{
	if(ll>lr)
	return;
	int pos;
	int t=front[ll];
	for(int i=rl;i<=rr;i++)
	{
		if(mid[i]==t)
		{
			pos=i;
			break;
		}
	}
	fun(ll+1,ll+pos-rl,rl,pos-1);
	fun(ll+pos-rl+1,lr,pos+1,rr);
	cout<<t<<' ';
}

int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>front[i];
	for(int i=0;i<n;i++)
		cin>>mid[i];
	fun(0,n-1,0,n-1);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

给前序和中序，层序输出

#include
using namespace std;
int pre[35],in[35],ltree[35],rtree[35];
int n;
queue<int>q;

int build(int l1,int r1,int l2,int r2)
{
	if(l1>r1) return 0;
	int root=pre[l2];
	int pos=l1;
	while(in[pos]!=root) pos++;
	int len=pos-l1;
	ltree[root]=build(l1,pos-1,l2+1,l2+len);
	rtree[root]=build(pos+1,r1,l2+len+1,r2);
	return root;
}

void level(int n)
{
	int root=pre[n];
	cout<<root;
	if(ltree[root]) q.push(ltree[root]);
	if(rtree[root]) q.push(rtree[root]);
	while(q.size())
	{
		int now=q.front();
		q.pop();
		cout<<' '<<now;
		if(ltree[now]) q.push(ltree[now]);
		if(rtree[now]) q.push(rtree[now]);
	}
}


int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%d",&in[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&pre[i]);
	build(1,n,1,n);
	level(1);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

后序和中序构造二叉树
本题目要求用后序序列和中序序列构造一棵二叉树（树中结点个数不超过10个），并输出其先序序列。

#include
using namespace std;
int n;
int mid[11],back[11];
void fun(int ll,int lr,int rl,int rr)
{
	if(ll>lr)
	return;
	cout<<back[lr]<<' ';
	int pos;
	int t=back[lr];
	for(int i=rr;i>=rl;i--)
	{
		if(mid[i]==t)
		{
			pos=i;
			break;
		}
	}
	fun(ll,pos+ll-rl-1,rl,pos-1);
	fun(pos+ll-rl,lr-1,pos+1,rr);
}

int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>back[i];
	for(int i=0;i<n;i++)
		cin>>mid[i];
	fun(0,n-1,0,n-1);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

给中序和后序，层序输出

#include
using namespace std;
int in[35],post[35],ltree[35],rtree[35];
int n;
queue<int>q;

int build(int l1,int r1,int l2,int r2)
{
	//第1,2,3,4个参数分别为所要建的树的中序左端点，中序右端点，后序左端点，后序右端点 
	if(l1>r1) return 0;
	int root=post[r2];
	int pos=l1;
	while(in[pos]!=root) pos++;//在中序中找到（相对的）根结点的位置，在该位置左边的为左子树序列，右边的为右子树序列 
	int len=pos-l1;
	ltree[root]=build(l1,pos-1,l2,l2+len-1);//建左子树 
	rtree[root]=build(pos+1,r1,l2+len,r2-1);//建右子树 
	return root;//该点是上一层的左孩子or右孩子，返回到上层 
}

void level(int n)
{
	int root=post[n];//后序的最后一个为总的根结点 
	cout<<root;
	if(ltree[root]) q.push(ltree[root]);
	if(rtree[root]) q.push(rtree[root]);
	while(q.size())
	{
		int now=q.front();
		q.pop();
		cout<<' '<<now;
		if(ltree[now]) q.push(ltree[now]);
		if(rtree[now]) q.push(rtree[now]);
	}
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%d",&post[i]);//输入后序 
	for(int i=1;i<=n;i++)
		scanf("%d",&in[i]);//输入中序 
	build(1,n,1,n);//建树 
	level(n);//层序输出 
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

9.4.2 二叉堆

在这里插入图片描述

#include 
using namespace std;
 
int now,tail=0;
int heap[1000001];
 
void insert(int x)
{
	heap[++tail]=x;//从尾端入堆 
	int now=tail;
	while(now>1)//控制不越界，1的位置是根结点 
	{
		int fa=now/2;//父结点下标 
		if(heap[fa]<=heap[now]) return;//终止条件：父结点值小于等于当前位置的值，无需继续交换 
		swap(heap[fa],heap[now]);
		now=fa;//向上继续 
	}
}
void de()
{
	heap[1]=heap[tail--];//删除根结点，将堆结尾的数交换到根结点 
	now=1;
	while(now*2<=tail)//控制不越界 
	{
		int next=now*2;//next是左儿子，next+1是右儿子 
		if(next<tail&&heap[next+1]<heap[next]) next++;
		//右儿子存在，且其值小于左二子->当前位置与右儿子比较，否则与左儿子比较 
		if(heap[now]<=heap[next]) return;//终止条件：当前结点值小于等于儿子结点的值，无需继续交换 
		swap(heap[now],heap[next]);
		now=next;//向下继续 
	}
}
int main()
{
	int n,x,y;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		if(x==1)
		{
			scanf("%d",&y);
			insert(y);
		}
		if(x==2) printf("%d\n",heap[1]);
		if(x==3) de();
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;
int n,op,x;
 
int main()
{
	cin>>n;
	while(n--)
	{
		scanf("%d",&op);
		if(op==1) 
		{
			scanf("%d",&x);
			q.push(x);
		}
		if(op==2) printf("%d\n",q.top());
		if(op==3) q.pop();
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include
using namespace std;
int heap[1000010];
int n,op,x,k;
 
int main()
{
	cin>>n;
	while(n--)
	{
		scanf("%d",&op);
		if(op==1) 
		{
			scanf("%d",&x);
			heap[++k]=x;
 			push_heap(heap+1,heap+1+k,greater<int>());  
		}
		if(op==2) printf("%d\n",heap[1]);
		if(op==3)
		{
			 pop_heap(heap+1,heap+1+k,greater<int>());  
 			 k--;    
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

9.4.3 并查集

输入第一行为三个正整数，n、m和q。n结点数；m为给出的已知信息数量；q为查询数。接下来m行，每行2个正整数a和b，表示结点a和结点b属于同一集。接下来q行，每行2个正整数c和d，即查询结点c和d是否属于同一集。每行输入的整数以空格间隔，n、m、q均不超过1000。
输出为q+1行，前q行对应于输入的q个查询的结果，如果属于同一帮派，则输出“Yes”，否则输出“No”。最后一行为一个整数，表示集的数目。

#include
using namespace std;
int n,m,q;
int f[100010];
int find(int x)
{
	if(f[x]==x)
	return x;
	else
	return f[x]=find(f[x]);
}

int main()
{
	cin>>n>>m>>q;
	int a,b,x,y;
	int ans=n-m;
	for(int i=1;i<=n;i++)
		f[i]=i;
	while(m--)
	{
		cin>>a>>b;
		x=find(a);
		y=find(b);
		if(x!=y) f[x]=y;
	}
	while(q--)
	{
		cin>>x>>y;
		if(find(x)!=find(y))
			cout<<"No"<<endl;
		else
			cout<<"Yes"<<endl;
	}
	cout<<ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

在这里插入图片描述
边带权的并查集

#include
using namespace std;
int n,m;
const int N=5010;
int a[N*2],cnt=0,f1[N],d[N];
 
struct Node
{
	int x,y;
	int ans;
}node[N];
 
int find(int x)
{
	if(f1[x]==x) return f1[x];
	int root=find(f1[x]);
	d[x]^=d[f1[x]];
	return f1[x]=root;
}
 
int merge_1(int x,int y)
{
	int fx1=find(x),fy1=find(y);
	f1[fy1]=fx1;
}
 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		string s;
		scanf("%d%d",&node[i].x,&node[i].y);
		cin>>s;
		if(s=="even") node[i].ans=0;
		else node[i].ans=1;
		a[++cnt]=node[i].x-1;
		a[++cnt]=node[i].y;
	}
	sort(a+1,a+cnt+1);
	int total=unique(a+1,a+cnt+1)-(a+1);
	for(int i=1;i<=total;i++)
		f1[i]=i;
	for(int i=1;i<=m;i++)
	{
		int x=lower_bound(a+1,a+total+1,node[i].x-1)-a;
		int y=lower_bound(a+1,a+total+1,node[i].y)-a;
		int p=find(x),q=find(y);
		if(p==q)
		{
			if(d[x]^d[y]!=node[i].ans)
			{
				cout<<i-1<<endl;
				return 0;
			}
		}
		else
		{
			f1[p]=q;
			d[p]=d[x]^d[y]^node[i].ans;
		}
	}
	cout<<m<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

拓展域的并查集

#include
using namespace std;
int n,m;
const int N=5010;
int a[N*2],cnt=0,f1[N],f2[N];
 
struct Node
{
	int x,y;
	int ans;
}node[N];
 
int find(int x)
{
	if(f1[x]==x) return f1[x];
	else return f1[x]=find(f1[x]);
}
 
int merge_1(int x,int y)
{
	int fx1=find(x),fy1=find(y);
	f1[fy1]=fx1;
}
 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		string s;
		scanf("%d%d",&node[i].x,&node[i].y);
		cin>>s;
		if(s=="even") node[i].ans=0;
		else node[i].ans=1;
		a[++cnt]=node[i].x-1;//注意左端点对应的位置
		a[++cnt]=node[i].y;
	}
	sort(a+1,a+cnt+1);
	int total=unique(a+1,a+cnt+1)-(a+1);//离散化
	for(int i=1;i<=total*2;i++)
		f1[i]=i;//1~total对应奇偶性不同，total~2*total对应奇偶性相同
	for(int i=1;i<=m;i++)
	{
		node[i].x=lower_bound(a+1,a+total+1,node[i].x-1)-a;
		node[i].y=lower_bound(a+1,a+total+1,node[i].y)-a;
		if(node[i].ans==0)
		{
			     if(find(node[i].x+total)==find(node[i].y)||find(node[i].x)==find(node[i].y+total))
            //此前已有条件表明左右端点奇偶性不同
			{
				cout<<i-1<<endl;
				return 0;
			}
			merge_1(node[i].x,node[i].y);//合并左端点的奇数域和右端点的奇数域
			merge_1(node[i].x+total,node[i].y+total);//合并左端点的偶数域和右端点的偶数域
		}
		else
		{
			if(find(node[i].x+total)==find(node[i].y+total)||find(node[i].x)==find(node[i].y))
            //此前已有条件表明左右端点奇偶性相同
			{
				cout<<i-1<<endl;
				return 0;
			}
			merge_1(node[i].x+total,node[i].y);//合并左端点的偶数域和右端点的奇数域
			merge_1(node[i].x,node[i].y+total);//合并左端点的奇数域和右端点的偶数域
		}
	}
	cout<<m<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

在这里插入图片描述

#include
using namespace std;
int n,k,cnt;
int f[50010*3];
 
int find(int x)
{
	if(f[x]==x) return f[x];
	else return f[x]=find(f[x]);
}
 
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n*3;i++) f[i]=i;//1~n自身域，n~2*n捕食域，2*n~3*n被捕食域
	for(int i=1;i<=k;i++)
	{
		int op,x,y;
		scanf("%d%d%d",&op,&x,&y);
		if(x>n||y>n)
		{
			cnt++;
			continue;
		} 
		if(op==1)//x和y是同类
		{
			if(find(x+n)==find(y)||find(x)==find(y+n))//y在x的捕食域或者x在y的捕食域，矛盾
				cnt++;
			else
			{
				f[find(y)]=find(x);//合并x和y的自身域
				f[find(y+n)]=find(x+n);//合并x和y的捕食域
				f[find(y+2*n)]=find(x+2*n);	//合并x和y的被捕食域
			}
		}
		if(op==2)//x捕食y
		{
			if(find(x)==find(y)||find(x)==find(y+n))//y在x的自身域或者x在y的捕食域，矛盾
				cnt++;
			else 
			{
				f[find(y)]=find(x+n);//合并y的自身域和x的捕食域
				f[find(y+2*n)]=find(x);//合并y的被捕食域和x的自身域
				f[find(y+n)]=find(x+2*n);//合并y的捕食域和x的被捕食域
			}
		}
	}
	cout<<cnt<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

9.4.4 树状数组

在这里插入图片描述
单点修改、区间查询

#include
using namespace std;
long long c[1000010];
int n;
int lowbit(int x)
{
	return x&(-x);
}
void update(int j,int x)
{
	for(int i=j;i<=n;i+=lowbit(i))
	{
		c[i]+=x;
	}
}
long long get_sum(int add)
{
	long long ans=0;
	for(int i=add;i;i-=lowbit(i))
	{
		ans+=c[i];
	}
	return ans;
 
int main()
{
	int n,q,i;
	cin>>n>>q;
	for(i=1;i<=n;i++)
	{
		int a;
		scanf("%d",&a);
		update(i,a);
	}
	while(q--)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int j,x;
			cin>>j>>x;
			update(j,n,x);
		}
		if(op==2)
		{
			int l,r;
			cin>>l>>r;
			long long sum;
			sum=get_sum(r)-get_sum(l-1);
			cout<<sum<<endl;	
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

树状数组+差分
区间修改、单点查询

#include
using namespace std;
long long a[500005],dif[500005],c[500005];
int n,m;
int lowbit(int x)
{
	return x&(-x);
}
void update(int x,long long p)
{
	for(int i=x;i<=n;i+=lowbit(i))
		c[i]+=p;
}
long long get_sum(int x)
{
	long long sum=0;
	for(int i=x;i;i-=lowbit(i))
		sum+=c[i];
	return sum;
}
 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	while(m--)
	{
		int option;
		scanf("%d",&option);
		if(option==1)
		{
			int l,r;
			long long z;
			scanf("%d%d%lld",&l,r,&z);
			
			update(l,z);
			update(r+1,-z);
		}
		if(option==2)
		{
			int q;
			scanf("%d",&q);
			cout<<get_sum(q)+a[q]<<endl;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

树状数组求逆序对
任意给定一个集合a,用t[val]保存数值val1在集合a内出现的次数，那么数组t在[l,r]上的区间和 $\sum_{i=1} ^{r} t[i]$ 就表示集合a中范围在[l,r]内的数有多少个。可以在集合a的数值范围上建立一个树状数组来维护t的前缀和。

对于给定的序列a，倒序扫描之，对于每个数a[i]:

在树状数组中查询前缀和[1,a[i]-1]，累加到答案ans中（这些数比a[i]小，位置却在它之后）。
单点修改，t[a[i]]++，同时维护前缀和。

数值范围较大时可以先离散化。

#include
using namespace std;
const int N=200010;
int n,pos[N],love[N],seat[N],c[N],ans[N];

int lowbit(int x)
{
	return x&(-x);
}

void add(int p)
{
	for(int i=p;i<=n;i+=lowbit(i))
		c[i]++;
}

int get(int p)
{
	int sum=0;
	for(int i=p;i;i-=lowbit(i))
		sum+=c[i];
	return sum;
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d%d",&x,&love[i]);
		pos[x]=i;
	}
	for(int i=1;i<=n;i++)
		seat[i]=pos[love[i]];
	for(int i=n;i;i--)
	{
		ans[i]+=get(seat[i]);
		add(seat[i]);
	}
	memset(c,0,sizeof(c));
	for(int i=1;i<=n;i++)
	{
		ans[i]+=get(n)-get(seat[i]);
		add(seat[i]);
		printf("%d\n",ans[i]);
	}
	return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

9.4.5 LCA

倍增法

操作步骤：
求出倍增数组；
把两个点移动到同一深度；
逐步试探出LCA。

#include
using namespace std;
struct Edge
{
	int to,next;
}edge[500005*2];//无向图，两倍开 
int head[500005],grand[500005][21],depth[500005],lg[500001];
int cnt,n,m,s;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

void add(int x,int y)
{
	edge[++cnt].to=y;
	edge[cnt].next=head[x];
	head[x]=cnt;
}

void dfs(int now,int fa)
{
	depth[now]=depth[fa]+1;
	grand[now][0]=fa;
	for(int i=1;i<=lg[depth[now]];i++)
	//for(int i=1;(1<
		grand[now][i]=grand[grand[now][i-1]][i-1];
		//爸爸的爸爸叫爷爷~~~ 
	for(int i=head[now];i;i=edge[i].next)
	//遍历和当前结点相连的所有的边（按输入的倒序），最后一条边的 edge[i].next==0
	{
		cout<<"第"<<i<<"条边,指向" <<edge[i].to<<endl; 
		if(edge[i].to!=fa)
			dfs(edge[i].to,now);
	}
}

int LCA(int a,int b)
{
	if(depth[a]<depth[b])
		swap(a,b);
	while(depth[a]>depth[b])
		a=grand[a][lg[depth[a]-depth[b]]-1];
	//倍增法逼近，e.g:depth[a]-depth[b]==14
	//lg[depth[a]-depth[b]]-1==3,a上升8个深度，depth[a]-depth[b]==6； 
	//lg[depth[a]-depth[b]]-1==2,a上升4个深度，depth[a]-depth[b]==2； 
	//lg[depth[a]-depth[b]]-1==1,a上升2个深度，depth[a]-depth[b]==0； 
	if(a==b) return a;//a和b的LCA就是a 
	for(int k=lg[depth[a]]-1;k>=0;k--)
		if(grand[a][k]!=grand[b][k])
			a=grand[a][k],b=grand[b][k];
	//从远古祖先(注意不要越界）中逐渐向最近的试探 
	// e.g:depth[a]==14,depth[LCA]==7;
	// k=lg[depth[a]]-1,k==3;grand[a][k]==grand[b][k];continue;
	//k==2,grand[a][k]!=grand[b][k],a,b一起向上4个深度；
	//k==1,grand[a][k]!=grand[b][k],a,b一起向上2个深度；
	//k==0,grand[a][k]!=grand[b][k],a,b一起向上1个深度； 
	//一共向上4+2+1==7个深度，找到LCA 
	return grand[a][0];
}

int main()
{
	n=read(),m=read(),s=read();
	for(int i=1;i<n;i++)
	{
		int a,b;
		a=read(),b=read();
		add(a,b);
		add(b,a);
	}
	for(int i=1;i<=n;i++)
		lg[i]=lg[i-1]+((1<<lg[i-1])==i);//log_{2}{i}+1
	dfs(s,0);//从根结点开始搜索 
	while(m--)
	{
		int x,y;
		x=read(),y=read();
		printf("%d\n",LCA(x,y));
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

RMQ+ST

操作步骤：

DFS求出欧拉序列和深度序列，以及每个结点在欧拉序列中第一次出现的位置；
找到查询的两个结点在欧拉序列中第一次出现的位置；
在深度序列中两个位置之间的区间找到深度最小的点。
P.S.:假如两个结点在欧拉序列中不止出现一次，只需要任选其中一次来计算即可

//3.95s /  227.49MB /  1.67KB C++14 (GCC 9) O2

#include
using namespace std;
const int N=500005;
vector<int>vec[N];
//记录每个结点可以走向哪些结点 
int f[N*2][21],mem[N*2][21],depth[N*2],first[N],vis[N*2],lg[N];
//f:记录深度序列区间中的最小深度
//mem:记录 找到深度序列区间中的最小深度 时的对应结点（在欧拉序列中） 
//depth:在dfs过程中记录遍历到每个点时的对应深度
//first:记录每个结点第一次出现时在欧拉序列中的位置
//vis:欧拉序列
//lg；lg[i]==log_{2}{i}+1 
int cnt=0,n,m,s;
//cnt:每走到一个点计一次数
 
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
} 

void dfs(int now,int dep)
{
	if(!first[now]) first[now]=++cnt;//第一次遍历到该点 
	depth[cnt]=dep,vis[cnt]=now;
	for(int i=0;i<vec[now].size();i++)
	{
		if(first[vec[now][i]]) continue;//是该结点的父节点，跳过 
		else dfs(vec[now][i],dep+1);
		++cnt;
		depth[cnt]=dep,vis[cnt]=now;//深搜完了vec[now][i]下的分支，回到当前结点 now
	}
}

void RMQ()
{
	for(int i=1;i<=cnt;i++)
	{
		lg[i]=lg[i-1]+((1<<lg[i-1])==i);
		f[i][0]=depth[i];//区间长度为1时，该区间内深度的最小值就是该结点的深度 
		mem[i][0]=vis[i];
	}
	for(int j=1;(1<<j)<=cnt;j++)//枚举的区间长度倍增 
		for(int i=1;i+(1<<j)-1<=cnt;i++)//枚举合法的每个区间起点 
		{
			if(f[i][j-1]<f[i+(1<<(j-1))][j-1])//深度最小的点在前半个区间 
			{
				f[i][j]=f[i][j-1];
				mem[i][j]=mem[i][j-1];
			}
			else//深度最小的后半个区间 
			{
				f[i][j]=f[i+(1<<(j-1))][j-1];
				mem[i][j]=mem[i+(1<<(j-1))][j-1];
			}
		}
}

int ST(int x,int y)
{
	int l=first[x],r=first[y];//找到输入的两个结点编号对应在欧拉序列中第一次出现的位置 
	if(l>r) swap(l,r);
	int k=lg[r-l+1]-1;
	if(f[l][k]<f[r-(1<<k)+1][k]) return mem[l][k];
	else return mem[r-(1<<k)+1][k];
}

int main()
{
	n=read(),m=read(),s=read();
	for(int i=1;i<n;i++)
	{
		int a,b;
		a=read(),b=read();
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	dfs(s,0);//打表，给first、depth、vis赋值，给RMQ奠定基础 
	/*cout<<"各结点第一次出现的位置："<
	RMQ();//打表，给f和mem赋值 ,给ST奠定基础 
	while(m--)
	{
		int x,y;
		x=read(),y=read();
		printf("%d\n",ST(x,y));
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

9.4.6 线段树

线段树是一种基于分治思想的二叉树结构，用于在区间上进行统计。每个节点代表一个区间，对于每个内部节点[l,r]（编号p），左子节点代表区间[l,mid]（编号2p），右子节点代表区间[mid+1,r]（编号2p+1）.可以用结构体数组保存一棵线段树，数组大小开到N*4
在这里插入图片描述
P2068 统计和

定义线段树

struct segment_tree
{
	int l,r;
	long long sum;
}tree[100010*4];
1
2
3
4
5

建树

void build(int p,int l,int r)
{
	tree[p].l=l,tree[p].r=r,tree[p].sum=0;
	if(l==r) return;//到达根节点 
	int mid=(l+r)/2;
	build(p*2,l,mid);//左子树 
	build(p*2+1,mid+1,r);//右子树 
}

1
2
3
4
5
6
7
8
9

单点修改

void change(int p,int x,int v)
{
	if(tree[p].l==tree[p].r)//到达对应单点（左右端点值都为x） 
	{
		tree[p].sum+=v;//修改 
		return;
	}
	int mid=(tree[p].l+tree[p].r)/2;
	if(x<=mid) change(p*2,x,v);//单点在左子树 
	else change(p*2+1,x,v);//单点在右子树 
	tree[p].sum=(tree[p*2].sum+tree[p*2+1].sum);//合并 
}

1
2
3
4
5
6
7
8
9
10
11
12
13

区间查询

假设当前询问的区间为[l,r]
递归到一个区间[tl,tr]时,有四种情况：

$l <= tl <= t r <= r$ ,该区间被完全覆盖在询问区间内，直接返回[tr,tl]上的和；
$tl <= l <= t r <= r$ ,当前区间的右边一部分在询问区间内，判断l与mid=(tr+tl)/2的大小关系，若l>mid，只需递归右子树，否则需要递归左右子树（右子树会在递归后直接返回）
$l <= tl <= r <= t r$ ,参考上一条
$t r <= l <= r <= t r$ ，递归左右子树

long long ask(int p,int l,int r)
{
    if(l<=tree[p].l&&r>=tree[p].r) 
		return tree[p].sum;//如果整个区间被覆盖，就返回维护的值
    int mid=(tree[p].l+tree[p].r)>>1;
    long long ans=0;
    if(l<=mid) ans+=ask(p*2,l,r);
    if(r>mid) ans+=ask(p*2+1,l,r);//累加答案，返回左右儿子的和
    return ans;
}
1
2
3
4
5
6
7
8
9
10

完整代码

#include
using namespace std;

struct segment_tree
{
	int l,r;
	long long sum;
}tree[100010*4];

void build(int p,int l,int r)
{
	tree[p].l=l,tree[p].r=r,tree[p].sum=0;
	//cout<<"p:"<
	if(l==r) return;//到达根节点 
	int mid=(l+r)/2;
	build(p*2,l,mid);//左子树 
	build(p*2+1,mid+1,r);//右子树 
}

void change(int p,int x,int v)
{
	if(tree[p].l==tree[p].r)//到达对应单点（左右端点值都为x） 
	{
		tree[p].sum+=v;//修改 
		return;
	}
	int mid=(tree[p].l+tree[p].r)/2;
	if(x<=mid) change(p*2,x,v);//单点在左子树 
	else change(p*2+1,x,v);//单点在右子树 
	tree[p].sum=(tree[p*2].sum+tree[p*2+1].sum);//合并 
}

long long ask(int p,int l,int r)
{
    if(l<=tree[p].l&&r>=tree[p].r) 
		return tree[p].sum;//如果整个区间被覆盖，就返回维护的值
    int mid=(tree[p].l+tree[p].r)>>1;
    long long ans=0;
    if(l<=mid) ans+=ask(p*2,l,r);
    if(r>mid) ans+=ask(p*2+1,l,r);//累加答案，返回左右儿子的和
    return ans;
}
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		char c; int x,y;
		cin>>c>>x>>y;
		if (c=='x') change(1,x,y);//单点修改 
		if (c=='y') printf("%lld\n",ask(1,x,y));//区间查询 
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

P3372 【模板】线段树 1

延迟标记
之前遇到区间修改时可能会遍历区间内的所有数，效率极其低下，有了线段树这种每个结点代表一个区间的数据结构，我们可以在结构体里新增一个变量add，用于储存对区间的增值操作，在未访问到这个区间时，我们可以不用管（这样就省掉了很多无用功233），如果访问到这个区间，就把这个区间对应的sum值加上（add*区间内点数），将add下放到左右两个子树，再将当前节点的add归零。
延迟标记的含义为“该节点曾经被修改，但其子节点尚未被更新”，其本身信息已被修改完毕。

void spread(int p)
{
	if(tree[p].add!=0)
	{
		tree[p*2].sum+=(tree[p*2].r-tree[p*2].l+1)*tree[p].add;=
		tree[p*2+1].sum+=(tree[p*2+1].r-tree[p*2+1].l+1)*tree[p].add;=
		tree[p*2].add+=tree[p].add;
		tree[p*2+1].add+=tree[p].add;
		tree[p].add=0;
	}
}
1
2
3
4
5
6
7
8
9
10
11

#include
using namespace std;

int n,m,a[100010];

struct segment_tree
{
	int l,r;
	long long sum,add;
}tree[100010*4];

void build(int p,int l,int r)
{
	tree[p].l=l,tree[p].r=r;
	if(l==r)
	{
		tree[p].sum=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}

void spread(int p)
{
	if(tree[p].add!=0)
	{
		tree[p*2].sum+=(tree[p*2].r-tree[p*2].l+1)*tree[p].add;=
		tree[p*2+1].sum+=(tree[p*2+1].r-tree[p*2+1].l+1)*tree[p].add;=
		tree[p*2].add+=tree[p].add;
		tree[p*2+1].add+=tree[p].add;
		tree[p].add=0;
	}
}

void change(int p,int l,int r,int x)
{
	if(l<=tree[p].l&&r>=tree[p].r)
	{
		tree[p].sum+=(long long)x*(tree[p].r-tree[p].l+1);
		tree[p].add+=x;
		return;
	}
	spread(p);//延迟标记
	int mid=(tree[p].l+tree[p].r)/2;
	if(l<=mid) change(p*2,l,r,x);
	if(r>mid) change(p*2+1,l,r,x);
	tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}

long long ask(int p,int l,int r)
{
    if(l<=tree[p].l && r>=tree[p].r) 
		return tree[p].sum;//如果被覆盖，就返回维护的值
    spread(p);//下传延迟标记，并查询左右儿子
    int mid=(tree[p].l+tree[p].r)>>1;
    long long ans=0;
    if(l<=mid) ans+=ask(p*2,l,r);
    if(r>mid) ans+=ask(p*2+1,l,r);//累加答案，返回左右儿子的和
    return ans;
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	build(1,1,n);
	while(m--)
	{
		int op,l,r;
		scanf("%d%d%d",&op,&l,&r);
		if(op==1)
		{
			int x;
			scanf("%d",&x);
			change(1,l,r,x);
		}
		else if(op==2)
			printf("%lld\n",ask(1,l,r));
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

9.4.7 字典树

Trie 是一种用于实现字符串快速检索的多叉树结构。Trie的每个结点都拥有若干个字符指针，若在插入或检索字符串时扫描到一个字符c，就沿着当前节点的c字符指针，走向该指针的结点。
在这里插入图片描述
看题目的描述很容易联想到当时学的归并排序求逆序对数，但是这里并不是一些有大小顺序的数而是很多字符串，怎么办呢？

$f (s t r in g) - > n u mb er$

我们可以采取很多种映射的办法，最直接的是map，其他的一些比如哈希等，这里采用字典树，插入时走到字符串末尾时给每个字符串一个编号，重排之后原有的顺序被打乱，归并排序的时候顺便求一下逆序对数就好啦。

#include
using namespace std;

const int N=5e5+10;
int n,tot,trie[N][100],a[N],b[N],temp[N];
long long ans;
void insert(string s,int x)
{
	int p=0,len=s.size();
	for(int i=0;i<len;i++)
	{
		if(!trie[p][s[i]-'A'])
			trie[p][s[i]-'A']=++tot;
		p=trie[p][s[i]-'A'];
	}
	a[p]=x;
}

void query(string s,int x)
{
	int p=0,len=s.size();
	for(int i=0;i<len;i++)
		p=trie[p][s[i]-'A'];
	b[x]=a[p];
}

void merge_sort(int l,int r)
{
	if(l==r) return;
	int mid=(l+r)>>1;
	merge_sort(l,mid);
	merge_sort(mid+1,r);
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r)
	{
		if(b[i]<=b[j]) temp[k++]=b[i++];
		else temp[k++]=b[j++],ans+=mid-i+1;
	}
	while(i<=mid) temp[k++]=b[i++];
    while(j<=r) temp[k++]=b[j++];
    for(int p=l;p<=r;p++) b[p]=temp[p];
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		string name;
		cin>>name;
		insert(name,i);
	}
	for(int i=1;i<=n;i++)
	{
		string name;
		cin>>name;
		query(name,i);
	}
	//for(int i=1;i<=n;i++)
		//cout<
	merge_sort(1,n);
    cout<<ans;
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

在这里插入图片描述

暴力的做法是对于每一个数，枚举其他所有数，求出(n-1)个异或值，有了字典树之后可以快速找到跟当前数异或值最大的那个。把这些01串都插入字典树，然后枚举这n个数，在这n个数对应找出的异或值中选最大的就行了。
怎么找到一个数对应的最大异或值呢？从高位（树根）开始每次都进入反子树（比如101011，第一次进入0子树，第二次进入1子树，第三次进入0子树，以此类推），如果想要进入的子树为空的话就迫不得已进入同子树。这样可以尽可能地选取到异或值大的数。每向下移一层，异或值乘2，如果进入反子树异或值加1。

#include
using namespace std;

const int N=1e5+10;
int n,trie[N*32][2],tot,a[N];
int maxn=0;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

void insert(int x)
{
	int p=0;
	for(int i=31;i>=0;i--)
	{
		int t=(x>>i)&1;
		if(!trie[p][t])
			trie[p][t]=++tot;
		p=trie[p][t];
	}
}

int query(int x)
{
	int q=0,ans=0,t;
	for(int i=31;i>=0;i--)
	{
		t=(x>>i)&1;//取出当前位
		if(!trie[q][!t])//反子树为空
		{
			q=trie[q][t];
			ans<<=1;
		}
		else
		{
			q=trie[q][!t];//进入反子树
			ans<<=1;
			ans+=1;//0^1=1
		}
	} 
	return ans;
}
int main()
{
	n=read();
	for(int i=0;i<n;i++)
	{
		a[i]=read();
		insert(a[i]);
	}
	for(int i=0;i<n;i++)
	{
		int temp=query(a[i]);
		maxn=max(maxn,temp);
	}
	cout<<maxn;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

9.4.8 哈夫曼树

哈夫曼树：带权路径长度WPL最短的多叉树（最优多叉树）

考虑构造一棵包含n个叶子结点的k叉树，其中第i个叶子节点带有权值 $w_i$ ，要求最小化 $\sum{w_i*l_i}$ ,其中 $l_i$ 表示第i个叶子节点到根节点的距离。
在这里插入图片描述
——李煜东《算法竞赛进阶指南》

哈夫曼编码原则： n个节点的哈夫曼树含有2n-1个节点，没有度为1的节点编码从叶子节点到根节点，译码从根节点到叶子节点。

从哈夫曼树根节点开始，对左子树分配码“0”，右子树分配码“1”，一直到达叶子节点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。

例子

一篇电文，原文为：AMCADEDDMCCAD。现在要把原文转换成01串发送给对方。为了节省资源，我们当然希望翻译好的01串长度尽量的短。怎么办？

研究发现：1、只有5个字母E,M,C,A,D； 2、这5个字母的使用频度分别为｛E,M,C,A,D｝= ｛1,2,3,3,4｝。
用频度为权值生成哈夫曼树，并在叶子上标注对应的字母，在树枝上标注分配码“0”或“1”（注：分配码不是边的长度，而是区分左右孩子代表方向）:

各字母的编码即为哈夫曼编码： EMCAD
所有编码长度和为12位，即PL=12，此时的PL并不是最小的，但此时的WPL一定是最小的。WPL最小才能使得密报翻译的01串长度最短。

P.S.解码：
正向最大匹配算法：
。字典中最长的key的长度是n
。从左往右扫描要解码的文本：第一次扫描n个字符，如果字典中有匹配的key则用该key对应的value替换这n个字符，如果无匹配的key则n=n-1，再次扫描

P2168 [NOI2015] 荷马史诗
在这里插入图片描述

#include
using namespace std;
#define ll long long

struct Node
{
	ll w,h;
	bool operator <(const Node &a)const
	{
		if(a.w!=w) return a.w<w;
		else return a.h<h;
	}
};
ll n,k,ans;
priority_queue<Node>q;

int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		ll x;
		scanf("%lld",&x);
		q.push(Node{x,1});
	}
	while((q.size()-1)%(k-1)!=0)//补成一个完整的哈夫曼树
		q.push(Node{0,1});
	while(q.size()>=k)
	{
		ll sum=0,high=-1;
		for(int j=1;j<=k;j++)
		{
			Node temp=q.top();
			q.pop();
			high=max(high,temp.h);//务必求出最大高度！
			sum+=temp.w;
		}
		ans+=sum;
		//cout<<"ans:"<
		//cout<<"sum:"<
		q.push(Node{sum,high+1});
	}
	printf("%lld\n%lld",ans,q.top().h-1);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

PTA-哈夫曼编码（30分）

给定一段文字，如果我们统计出字母出现的频率，是可以根据哈夫曼算法给出一套编码，使得用此编码压缩原文可以得到最短的编码总长。然而哈夫曼编码并不是唯一的。例如对字符串"aaaxuaxz"，容易得到字母 ‘a’、‘x’、‘u’、‘z’ 的出现频率对应为 4、2、1、1。我们可以设计编码 {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}，也可以用另一套 {‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}，还可以用 {‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101}，三套编码都可以把原文压缩到 14 个字节。但是 {‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001} 就不是哈夫曼编码，因为用这套编码压缩得到 00001011001001 后，解码的结果不唯一，“aaaxuaxz” 和 “aazuaxax” 都可以对应解码的结果。本题就请你判断任一套编码是否哈夫曼编码。

输入
首先第一行给出一个正整数 N（2≤N≤63），随后第二行给出 N 个不重复的字符及其出现频率，格式如下：

c[1] f[1] c[2] f[2] ... c[N] f[N]
1
1
2

其中c[i]是集合{‘0’ - ‘9’, ‘a’ - ‘z’, ‘A’ - ‘Z’, ‘_’}中的字符；f[i]是c[i]的出现频率，为不超过 1000 的整数。再下一行给出一个正整数 M（≤1000），随后是 M 套待检的编码。每套编码占 N 行，格式为：

c[i] code[i]
1
1
2

其中c[i]是第i个字符；code[i]是不超过63个’0’和’1’的非空字符串。

输出
对每套待检编码，如果是正确的哈夫曼编码，就在一行中输出"Yes"，否则输出"No"。

注意：最优编码并不一定通过哈夫曼算法得到。任何能压缩到最优长度的前缀编码都应被判为正确。

最优编码并不一定通过哈夫曼算法得到，但是哈夫曼算法得到的一定是最优编码，由此计算得到的带权路径长度(WPL)便是最短的。先将输入中的各大编码方式计算出其对应的带权路径长度之和，与通过哈夫曼算法得到的WPL进行比较，完成第一轮筛选。若是与哈夫曼算法得到的WPL相等，那么再对该编码方式进行前缀判定，存在前缀包含则判错（如果一个字母的编码是另一个字母编码的前缀，解码的结果就不唯一），否则输出Yes。

#include
using namespace std;

int c[100],f[100],n,m,WPL;
string code[100];//存储序列
char ch[100];
map<char,int> mp;
priority_queue<int,vector<int>,greater<int> >q;


bool judge()
{
	int a,b,sum=0;
	for(int i = 0;i<n;++i)
	{
		for(int j = i+1;j<n;++j)
		{
			a = code[i].find(code[j]);
			//前缀判断，返回code[j]在code[i]中存在的第一个位置，不存在则返回-1 
			b = code[j].find(code[i]);
			//cout<
			if(!a||!b)	return false;
		}
		sum+=mp[ch[i]]*code[i].length();//计算当前wpl
	}
	//cout<<"sum"<
	if(sum==WPL) return true;
	else return false;
}

int main()
{
	cin>>n;
	for(int i = 0;i<n;++i)
	{
		scanf(" %c %d",&c[i],&f[i]);
		q.push(f[i]);
		mp[c[i]] = f[i];//存储字母的权值
	}
	while(q.size()>1)
	{
		int a=q.top();
		q.pop();
		int b=q.top();
		q.pop();
		WPL+=(a+b);
		q.push(a+b);
	}
	//cout<<"WPL"<
	cin>>m;
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<n;j++)
		{
			scanf(" %c",&ch[j]);
			cin>>code[j];
		}
		if(judge()) cout <<"Yes"<<endl;
		else cout <<"No"<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

9.5 图

图的创建
请编写程序创建一个有向图。有向图中包含n个顶点，编号为0至n-1。

输入格式:
输入第一行为两个正整数n和e，分别表示图的顶点数和边数，其中n不超过20000，e不超过20000。接下来e行表示每条边的信息，每行为3个非负整数a、b、c，其中a和b表示该边的端点编号，c表示权值。各边并非按端点编号顺序排列。

输出格式:
按顶点编号递增顺序输出每个顶点引出的边，每个顶点占一行，若某顶点没有引出边，则不输出。每行表示一个顶点引出的所有边，格式为a:(a,b,w)……，表示有向边a->b的权值为w，a引出的多条边按编号b的递增序排列。

#include   
using namespace std;  
vector<int>v[20010];  
int m,adj[20010],temp[20010],mem[20010];  
struct edge  
{  
    int to;  
    int next;  
    int w;  
}e[20010];  
void add(int x,int y,int z)  
{  
    ++m;  
    v[x].push_back(m);  
    e[m].to=y;  
    e[m].next=x;  
    e[m].w=z;  
}  
  
int main()  
{  
    int n,ed,i;  
     cin>>n>>ed;  
    for(i=1;i<=ed;i++)  
    {  
        int x,y,z;  
        scanf("%d%d%d",&x,&y,&z);  
        add(x,y,z);  
    }  
    //for(i=0;i
        //cout<
    for(i=0;i<n;i++)  
    {  
        memset(temp,0,sizeof(temp));  
        memset(mem,0,sizeof(mem));  
        if(v[i].size())  
        {  
            int cap=v[i].size();  
            for(int j=0;j<cap;j++)  
            {  
                temp[j]=e[v[i][j]].to;  
                mem[temp[j]]=e[v[i][j]].w;  
            }  
            sort(temp,temp+cap);  
            cout<<i<<':';  
            for(int j=0;j<cap;j++)  
                cout<<"("<<i<<","<<temp[j]<<","<<mem[temp[j]]<<")";  
            cout<<endl;  
        }  
    }  
    return 0;  
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

9.6 分块

在这里插入图片描述

#include
using namespace std;
const int N=100010;

long long a[N],sum[N],add[N];
int l[N],r[N],pos[N];
int n,m,t;

void change(int L,int R,long long plus)
{
	int p=pos[L],q=pos[R];
	if(p==q)
	{
		for(int i=L;i<=R;i++)
			a[i]+=plus;
		sum[p]+=plus*(R-L+1);
	}
	else
	{
		for(int i=p+1;i<=q-1;i++)
			add[i]+=plus;
		for(int i=L;i<=r[p];i++)
			a[i]+=plus;
		sum[p]+=(r[p]-L+1)*plus;
		for(int i=l[q];i<=R;i++)
			a[i]+=plus;
		sum[q]+=(R-l[q]+1)*plus;
	}
}

long long ask(int L,int R)
{
	long long ans=0;
	int p=pos[L],q=pos[R];
	if(p==q)
	{
		for(int i=L;i<=R;i++)
			ans+=a[i];
		ans+=add[p]*(R-L+1);
	}
	else
	{
		for(int i=p+1;i<=q-1;i++)
			ans+=sum[i]+add[i]*(r[i]-l[i]+1);
		for(int i=L;i<=r[p];i++)
			ans+=a[i];
		ans+=add[p]*(r[p]-L+1);
		for(int i=l[q];i<=R;i++)
			ans+=a[i];
		ans+=add[q]*(R-l[q]+1);
	}
	return ans;
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	t=sqrt(n);
	for(int i=1;i<=t;i++)
	{
		l[i]=(i-1)*sqrt(n)+1;
		r[i]=i*sqrt(n);
	}
	if(r[t]<n)
	{
		t++;
		l[t]=r[t-1]+1;
		r[t]=n;
	}
	for(int i=1;i<=t;i++)
	{
		for(int j=l[i];j<=r[i];j++)
		{
			pos[j]=i;
			sum[i]+=a[j];
		}
	}
	while(m--)
	{
		char op[3];
		int L,R;
		long long plus;
		scanf("%s%d%d",op,&L,&R);
		if(op[0]=='C')
		{
			scanf("%lld",&plus);
			change(L,R,plus);
		}
		else printf("%lld\n",ask(L,R));
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

莫队
询问若干个区间内的情况：将这些区间重新排序，尽量让前一个区间跳到后一个区间时变化较小。

如何排序？
先把所有询问[l,r]读入，把这些询问按照左端点递增排序，然后分成 $\sqrt{N}$ 块。每块内部再按照右端点排序。

bool cmp(section x,section y)
{
	if(x.pos==y.pos) return x.r<y.r;
	else return x.pos<y.pos;
}
1
2
3
4
5

	int t=sqrt(n);
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<=m;i++)
	{
		sec[i].l=read();
		sec[i].r=read();
		sec[i].pos=(sec[i].l-1)/t+1;
		sec[i].id=i;
	}
	sort(sec+1,sec+m+1,cmp);
1
2
3
4
5
6
7
8
9
10
11

这样一来，相邻两个询问的左端点变化在 $\sqrt{N}$ 以内，右端点变化是单调的。以上一次询问[L,R]为基础，,求[L’,R’]，只需要一步步转移，花费 $O(\sqrt{N})$ 处理左端点，花费 $O (N)$ 处理右端点，时间复杂度 $O(N\sqrt{N})$ 。区间已经被重新排序过，所以要先把答案储存下来，在区间原位置编号处输出。

	int pl=1,pr=0;
	long long temp=0;
	for(int i=1;i<=m;i++)
	{
		while(pl>sec[i].l) pl--,...;
		while(pr<sec[i].r) pr++,...;
		while(pl<sec[i].l) ...,pl++;
		while(pr>sec[i].r) ...,pr--;
		ans[sec[i].id]=temp;
	}
1
2
3
4
5
6
7
8
9
10

莫队题的特点：

不强制在线
$O(n^{3/2})$ 可过

相关阅读:
rpc报错com.netflix.hystrix.exception.HystrixRuntimeException
IDEA断点调试
 1.4_1 Axure RP 9 for mac 入门
 【毕业设计】基于javaEE+原生Servlet+MySql的村镇旅游网站设计与实现（毕业论文+程序源码）——村镇旅游网站
 【giszz笔记】产品设计标准流程【5】
JWFD开源工作流矩阵引擎测试版本BUG20231022修正代码
 Node.js 20.6支持.env配置文件，加入C++垃圾回收函式库Oilpan
spring高级源码50讲-43-50(spring续)
Java面试题-Redis-第一天（Redis简单介绍)
ssh服务攻防与加固
原文地址：https://blog.csdn.net/m0_60630928/article/details/126468096