考试只好随便骗骗分过去啦啦啦…..
正解是玄学线段树:
以每个操作为叶子节点,我们定义几个变量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
附上对拍
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 pair
14 map
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 }
手机扫一扫
移动阅读更方便
你可能感兴趣的文章