QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#504768#9104. Zayin and ForestXunwuqishi#TL 91ms39832kbC++201.9kb2024-08-04 15:44:542024-08-04 15:44:54

Judging History

你现在查看的是最新测评结果

  • [2024-08-04 15:44:54]
  • 评测
  • 测评结果:TL
  • 用时:91ms
  • 内存:39832kb
  • [2024-08-04 15:44:54]
  • 提交

answer

#include<bits/stdc++.h>
#define Alex std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);
#define int long long
#define double long double
const int QAQ = 0;
const double eps = 1e-10;
const int mod = 1e9 + 7;
const int N = 1e7 + 10;

inline int lowbit(int x)
{
	return x & (-x);
}
struct node {
	int l, r;
	int add, sum;
} tr[N << 1];


int n, m, idx, root;

void pushup(int p) 
{
	tr[p].sum = tr[tr[p].l].sum + tr[tr[p].r].sum;
}

void pushdown(int p, int l, int r) 
{
	if(tr[p].add) {
		int mid = l + r >> 1;
		tr[tr[p].l].sum += (mid - l + 1) * tr[p].add, tr[tr[p].l].add += tr[p].add;
		tr[tr[p].r].sum += (r - mid) * tr[p].add, tr[tr[p].r].add += tr[p].add;
		tr[p].add = 0;
	}
}


void modify(int &p, int l, int r, int ql, int qr, int k) 
{
	if(!p) p = ++idx;
	if(l >= ql && r <= qr) {
		tr[p].sum += (r - l + 1) * k;
		tr[p].add += k;
		return ;
	}
	pushdown(p, l, r);
	int mid = l + r >> 1;
	if(ql <= mid) modify(tr[p].l, l, mid, ql, qr, k);
	if(qr > mid) modify(tr[p].r, mid + 1, r, ql, qr, k);
	pushup(p);
}

int query(int p, int l, int r, int ql, int qr) 
{
	if(l >= ql && r <= qr) { return tr[p].sum; }
	int mid = l + r >> 1;
	pushdown(p, l, r);
	int v = 0;
	if(ql <= mid) v = query(tr[p].l, l, mid, ql, qr);
	if(qr > mid) v += query(tr[p].r, mid + 1, r, ql, qr);
	return v;
}

signed main()
{
	Alex;
	int _;
	_ = 1;
	while(_--)
	{
		std::cin>>n>>m;
		std::map<int,int> ma;
		root = 0;
		for(int i = 1;i <= m;i++)
		{
			int op;
			std::cin>>op;
			if(op == 1)
			{
				int x,v;
				std::cin>>x>>v;
                for(x;x <= n;x = x + lowbit(x))   
                {
				    modify(root, 1, n, x, x, v);
				}
			}else
			{
				int l,r;
				int ans = 0;
				std::cin>>l>>r;
                ans = query(root, 1, n, l, r);
                std::cout<<ans<<'\n';
			}
		}
	}
	return QAQ;
}

詳細信息

Test #1:

score: 100
Accepted
time: 91ms
memory: 39832kb

input:

1000000000 20000
2 384578735 526547442
1 64211261 592970906
1 512065247 448267721
1 44993150 127180320
1 880319036 927623947
1 170536687 572121854
1 896600029 804033011
1 666246328 754201635
1 654066651 179982083
2 240989825 984888006
2 372004567 858916479
2 76127818 98606736
1 181794163 902842353
1...

output:

0
43148875202
17613404710
0
32808578044
28190043566
15641637055
78276219892
14955165236
20262224725
105057452192
17002492367
57916137452
27165464255
72766353838
39458327919
38294102627
264448717384
0
70928519548
279674530483
88885017175
111664599432
69703816663
211506104092
104120007714
34403738515
...

result:

ok 6649 lines

Test #2:

score: -100
Time Limit Exceeded

input:

1000000000000000000 100000
1 384578735 526547442
1 64211261 592970906
1 512065247 448267721
1 44993150 127180320
1 880319036 927623947
1 170536687 572121854
1 896600029 804033011
2 666246328 931651408754201635
1 654066651 179982083
1 984888006 240989825
1 372004567 858916479
1 76127818 98606736
1 18...

output:

144205553442
497561506762
903930740555
878459229726
689906696633
859703313829
735231510045
1177875391120
1461659121798
1612314483744
2027462020547
1991476058156
2381861014705
2033973986301
2117738140401
2946661001323
2187638958334
2593068002437
1854182975909
2262561461341
3038788266419
3070435321746...

result: