QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#383062#3746. 千万别用树套树ucup-team1251AC ✓327ms30648kbC++171.6kb2024-04-08 21:19:232024-04-08 21:19:24

Judging History

This is the latest submission verdict.

  • [2024-04-08 21:19:24]
  • Judged
  • Verdict: AC
  • Time: 327ms
  • Memory: 30648kb
  • [2024-04-08 21:19:23]
  • Submitted

answer

#include<bits/stdc++.h>
#define int long long	
#define ull unsigned long long
using namespace std;
typedef pair<int,int>PII;
typedef array<int,3>ar;
typedef pair<int,double>PID;
typedef pair<string,string>PSS;
typedef pair<PII,int>PPI;
const ull mask = std::chrono::steady_clock::now().time_since_epoch().count();
const int N=2e5+5;
const int M=1e9+7;
const int base=131;
ull shift(ull x) //树哈希:映射函数 使用ull自然溢出
{
	x ^= mask;
	x ^= x << 13;
	x ^= x >> 7; 
	x ^= x << 17;
	x ^= mask;
	return x;
}
int tr[10][N];
int n;
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int w,int ran)
{
	for(;x<=n;x+=lowbit(x))
	{
		tr[ran][x]+=w;
	}
}
int get(int x,int ran)
{
	int ans=0;
	for(;x>0;x-=lowbit(x))
	{
		ans+=tr[ran][x];
	}
	return ans;
}
int en[N][10];
int st[N][10];
void solve()
{	
	int m;
	while(cin>>n>>m)
	{
		int cnt=0;
		for(int i=1;i<=m;i++)
		{
			int op,l,r;
			cin>>op>>l>>r;
			if(op==1)
			{
				cnt++;
				add(n-l+1,1,1);
				add(r,1,2);
				if(r-l+1<=3)
				{
					en[r][r-l+1]++;
					st[l][r-l+1]++;
				}
				en[r][4]++;
				st[l][4]++;
				
			}
			else 
			{
				int l1=get(l-1,2);
				int r1=get(n-(r+1)+1,1);
				int ne=cnt-l1-r1;
				int len=r-l+1;
				if(len==2)
				{
					ne-=en[l][4];
					ne-=st[r][4];
				}
				if(len==3)
				{
					ne-=en[l][4];
					ne-=st[r][4];
					ne-=st[l+1][4]+en[l+1][4]-st[l+1][1];
				}
				cout<<ne<<"\n";
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int k=1;k<=5;k++) en[i][k]=0,st[i][k]=0,tr[k][i]=0;
		}
	}
	
}
signed main()	
{
	ios::sync_with_stdio(0);
	//	cin.tie(0),cout.tie(0);
	int t=1;
	//		cin>>t;
	while(t--)
		solve();	
}
//1 1 4
//1 3 5
// 1 1 5
// 1 1 1

詳細信息

Test #1:

score: 100
Accepted
time: 327ms
memory: 30648kb

input:

100000 100000
1 48500 63742
1 43673 89780
1 6471 44388
1 68054 71541
1 30056 91431
1 49687 70537
2 46899 46900
1 5165 57954
1 85892 88481
2 18060 18062
2 45289 45289
1 18927 67848
1 17389 96139
1 63451 92197
1 15473 87341
1 15162 15744
1 76728 99645
2 48730 48731
2 20886 20888
1 9756 67424
1 23175 4...

output:

2
2
3
7
5
8
9
4
6
2
11
13
13
10
13
15
9
10
14
16
17
16
16
15
2
4
11
6
11
12
23
9
26
3
28
20
12
12
22
30
5
27
6
29
10
14
27
6
17
15
9
30
20
34
7
36
15
8
32
16
21
40
19
2
1
12
12
39
37
13
19
20
1
9
37
1
41
40
20
34
45
43
27
30
47
29
13
50
41
44
29
35
38
53
2
46
54
36
56
58
45
32
42
26
52
42
60
1
4
25
...

result:

ok 500497 numbers