【模拟8.10】Weed(线段树)
阅读原文时间:2023年07月10日阅读:2

考试只好随便骗骗分过去啦啦啦…..

正解是玄学线段树:

以每个操作为叶子节点,我们定义几个变量ce表示层数,h表示高度,add表示所减的层数

那么问题转化为单点修改的问题输出直接是根节点答案

但是我们发现合并区间很毒瘤

我们分两种情况:

设L为左儿子,R为右儿子。

1.T[L].ce

2.T[L].ce>T[R].add 我们需要将左子树后面的add个减去,我们自然想到了类似平衡树的****

查找后缀的操作,于是肝…..

开始时我的query计算有多少减去,但是WA20

因为少考虑一种情况:

你的左子树中假设左子树根结点为K,左儿子Lson,右儿子Rson

右儿子中也可能有剩余的add,

那么我们直接发现右面不够查左面是不行的………

听了toot大神的建议,我改为了查询还有多少留下

 if(t\[k\*2+1\].ce<ceng)  
 {  
      qq\_sum+=t\[k\*2+1\].h;  
      query\_sum(k\*2,l,mid,ceng-t\[k\*2+1\].ce+t\[k\*2+1\].add);  
 }

当发现右端点少时,向左端点转移还需要减去靠右的add个

然后就没啥了,注意细节就好

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #define int long long
8 #define MAXN 1000010
9 using namespace std;
10 int read()
11 {
12 int x=0;char c=getchar();
13 while(c<'0'||c>'9')c=getchar();
14 while(c>='0'&&c<='9') 15 { 16 x=(x<<1)+(x<<3)+(c^48); 17 c=getchar(); 18 } 19 return x; 20 } 21 struct node{int ce,h,add,l,r;}t[MAXN*2]; 22 int qq_sum;int m,q; 23 int orz[MAXN],mm[MAXN]; 24 void query_sum(int k,int l,int r,int ceng) 25 { 26 if(l==r) 27 { 28 if(ceng!=0)qq_sum+=t[k].h; 29 return ; 30 } 31 int mid=(l+r)>>1;
32 //printf("k=%lld l=%lld r=%lld\n",k,l,r);
33 if(t[k*2+1].cet[r].add)
53 {
54 t[k].ce=t[l].ce+t[r].ce-t[r].add;
55 qq_sum=0;
56 query_sum(l,t[l].l,t[l].r,t[r].add);
57 t[k].h=t[l].h+t[r].h-qq_sum;
58 t[k].add=t[l].add;
59 //printf("--t[k].ce=%lld t[k].h=%lld add=%lld\n",t[k].ce,t[k].h,t[k].add);
60 }
61 else
62 {
63 t[k].h=t[r].h;
64 t[k].ce=t[r].ce;
65 t[k].add=t[r].add+t[l].add-t[l].ce;
66 //printf("t[k].ce=%lld t[k].h=%lld add=%lld\n",t[k].ce,t[k].h,t[k].add);
67 }
68 //printf("-----------\n");
69 return ;
70 }
71 void build(int k,int l,int r)
72 {
73 t[k].l=l;t[k].r=r;
74 if(l==r)
75 {
76 orz[l]=read();mm[l]=read();
77 if(orz[l]==0)
78 {
79 t[k].ce=1;t[k].h=mm[l];
80 //printf("t[%lld].ce=%lld t[%lld].h=%lld\n",k,t[k].ce,k,t[k].h);
81 }
82 else
83 {
84 t[k].add=mm[l];
85 //printf("t[%lld].add=%lld\n",k,t[k].add);
86 }
87 return ;
88 }
89 int mid=(l+r)>>1;
90 build(k*2,l,mid);
91 build(k*2+1,mid+1,r);
92 updata(k);
93 }
94 void F_add(int k,int l,int orzz,int x)
95 {
96 if(t[k].l==t[k].r)
97 {
98 t[k].add=0;t[k].ce=0;t[k].h=0;
99 if(orzz==0)
100 {
101 t[k].ce=1;
102 t[k].h=x;
103 //printf("t[%lld].ce=%lld t[%lld].h=%lld\n",k,t[k].ce,k,t[k].h);
104 }
105 else
106 {
107 t[k].add=x;
108 //printf("t[%lld].add=%lld\n",k,t[k].add);
109 }
110 return ;
111 }
112 int mid=(t[k].l+t[k].r)>>1;
113 if(l<=mid)F_add(k*2,l,orzz,x);
114 else F_add(k*2+1,l,orzz,x);
115 updata(k);
116 }
117 signed main()
118 {
119 //freopen("text.in","r",stdin);
120 // freopen("kkk.out","w",stdout);
121 m=read();q=read();
122 //printf("build\n");
123 build(1ll,1ll,m);
124 //printf("t[1].h=%lld\n",t[1ll].h);
125 for(int i=1;i<=q;++i)
126 {
127 int x,y,z;
128 x=read();y=read();z=read();
129 F_add(1,x,y,z);
130 printf("%lld\n",t[1].h);
131 }
132 }

附上对拍

1 #include
2 using namespace std;
3 int main()
4 {
5 int c=0;
6 while(true)
7 {
8 system("./pai");//puts("ran work out");
9 system("./b");//puts("ac work out");
10 system("./kkk");//puts("kx work out");
11 if(system("diff -b -B b.out kkk.out"))
12 {
13 puts("WA");
14 return 0;
15 }
16 cout<<++c<<" ";
17 puts("AC");
18 }
19 return 0;
20 }
21 /*
22 g++ pai.cpp -o pai
23 ./pai
24 g++ b.cpp -o b
25 ./b
26 g++ kkk.cpp -o kkk
27 ./kkk
28 g++ ran.cpp -o ran
29 ./ran
30 */

随机数据生成

1 #include
2 using namespace std;
3 int random(int m)
4 {
5 return (long long)rand()*rand()%m;
6 }
7 int judge()
8 {
9 int x=rand();
10 if(x%2)return 1;
11 else return 0;
12 }
13 paire[100000];
14 map,bool>h;
15 int main()
16 {
17 freopen("text.in","w",stdout);
18 srand((unsigned)time(0));
19 int n=random(7)+1;
20 int m=10;
21 int q=10;
22 printf("%d %d\n",m,q);
23 for(int i=1;i<=m;++i)
24 {
25 printf("%d %d\n",judge(),random(10)+1);
26 }
27 for(int i=1;i<=q;++i)
28 {
29 printf("%d %d %d\n",random(m)+1,judge(),random(10)+1);
30 }
31 return 0;
32 }

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章