文章

68

粉丝

691

获赞

24

访问

546.9k

头像
树状数组+前缀和操作,scanf读入
P1643
发布于2020年6月1日 12:20
阅读数 6.1k

与之前某道题有点类似,

一开始用树状数组写,别人用线段树132ms,我树状数组2000+,惊呆了,把cin换成scanf也没用,然后神奇的操作来了,

        for (int i = 1; i <= Q; i++) {
            scanf("%d%d", &l, &r);//换成lld就会T
            v.push_back(que(i, l, r));
        }

我把输入的每个查询的端点l,r换成int变量,然后就ac了。。。

 

#define MAX 111111
#define inf 0x3f3f3f3f
#define ll long long
#define vec vector<int,int>
#define P pair<int,int>
int T, N, Q, l, r;
ll a[MAX], t[MAX];

void update(int x, ll k) {
	while (x <= N) {
		t[x] += k;
		x += x & -x;
	}
}

ll query(int x) {
	ll sum = 0;
	while (x > 0) {
		sum += t[x];
		x -= x & -x;
	}
	return  sum;
}

struct que {
	int id, l, r;
	ll cnt;
	que(int a = 0, int b = 0, int c = 0) { id = a, l = b, r = c; }
};

bool cmp(que q1, que q2) { return q1.r < q2.r; }
bool cmp1(que...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发