QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#383062 | #3746. 千万别用树套树 | ucup-team1251 | AC ✓ | 327ms | 30648kb | C++17 | 1.6kb | 2024-04-08 21:19:23 | 2024-04-08 21:19:24 |
Judging History
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