MnZn 刚学线段树,求救 /ll
  • 板块P2184 贪婪大陆
  • 楼主Elgo87
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/1/10 19:54
  • 上次更新2023/10/28 12:32:37
查看原帖
MnZn 刚学线段树,求救 /ll
393864
Elgo87楼主2022/1/10 19:54

RT,参考了第四篇题解的做法,虽然神是神奇,但是还是 WA 0pts 啊

#include <bits/stdc++.h>
using namespace std;

inline long long read() {
    long long num = 0, nev = 1;  char ch = getchar();
    while (!isdigit(ch)) { if (ch=='-') nev = -1; ch = getchar(); }
    while (isdigit(ch)) { num = (num<<1)+(num<<3)+(ch^48); ch = getchar(); }
    return num * nev;
}

inline void print(const long long& x) {
    if (x<0) {putchar('-'); print(-x); }
    if(x<10) putchar(x+48);
    else { print(x/10); putchar(x%10+'0'); }
}

const long long MAXN = 114514;

struct node {
	int left, right;
	int suml, sumr;
};

node tree[MAXN << 2];
long long n, m;

void build(int k, int l, int r)
{
	tree[k].left = l;
	tree[k].right = r;
	if (l == r) return ;
	
	int mid = l + r >> 1;
	build(k << 1, l, mid);
	build(k << 1 | 1, mid + 1, r);
	
	return ;
}

void modify_start(int k, int x)
{
	if (tree[k].left == tree[k].right)
	{
		tree[k].suml ++;
		return ;
	}
	
	if (x > tree[k<<1].right) modify_start(k<<1 |1, x);
	else modify_start(k << 1, x);
	
	tree[k].suml = tree[k<<1].suml + tree[k<<1 | 1].suml;
	return ;
}

void modify_end(int k, int x)
{
	if (tree[k].left == tree[k].right)
	{
		tree[k].sumr ++;
		return ;
	}
	
	if (x>tree[k<<1].right) modify_end(k << 1 |1, x);
	else modify_end(k << 1, x);
	
	tree[k].sumr = tree[k<<1].sumr + tree[k<<1 | 1].sumr;
	return ;
}

long long query_start(int k, int l, int r)
{
	if (r < tree[k].left || tree[k].right < l) {
		
		return 0;
		
	}
	if (l <= tree[k].left && tree[k].right <= r) {
		
		return tree[k].suml;
	}
	
	long long res = 0;
	res += query_start(k<<1, l, r);
	res += query_start(k<<1 | 1, l, r);
	return res;
}

long long query_end(int k, int l, int r)
{
	if (r > tree[k].left || tree[k].right < l) {
		return 0;
	} 
	if (l <= tree[k].left && tree[k].right <= r)
	{
		return tree[k].sumr;
	} 
	
	long long res = 0;
	res += query_end(k<<1, l, r);
	res += query_end(k<<1 | 1, l, r);
	return res;
}

int main()
{
	n = read();
	m = read();
	build(1,1,n);
	
	for (int i = 1; i <= m; i ++)
	{
		int op = read(), l = read(), r = read();
		if (op == 1) 
		{
			modify_start(1, l);
			modify_end(1, r);
			
			// for (int j = 1; j <= n<<2; j ++) cout << tree[j].suml << ' ';
			// putchar('\n');
		}
		else
		{
			printf("%lld\n", query_start(1,1,r)-query_end(1,1,l-1));
		}
	}
	return 0;
}

老规矩,悬赏一个贴贴(

2022/1/10 19:54
加载中...