PKU2019数据结构与算法实习作业 1~10

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int fa[50005];
int getfa(int x)
{
    return x == fa[x]? x : fa[x] = getfa(fa[x]);
}
int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        int ans = n;
        for(int i = 1; i <= n; i++)
            fa[i] = i;
        for(int i = 1; i <= m; i++)
        {
            int x, y;
            x = read(), y = read();
            int p = getfa(x), q = getfa(y);
            if(p == q)
                puts("Yes");
            else
            {
                puts("No");
                fa[q] = p;
                ans--;                
            }
        }
        printf("%d\n", ans);
        for(int i = 1; i <= n; i++)
            if(getfa(i) == i)
                printf("%d ", i);
        puts("");
    }
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n, m;

int fa[50005];

int getfa(int x)

{

return x == fa[x]? x : fa[x] = getfa(fa[x]);

}

int main()

{

while(scanf("%d%d", &n, &m) != EOF)

{

int ans = n;

for(int i = 1; i <= n; i++)

fa[i] = i;

for(int i = 1; i <= m; i++)

{

int x, y;

x = read(), y = read();

int p = getfa(x), q = getfa(y);

if(p == q)

puts("Yes");

else

{

puts("No");

fa[q] = p;

ans--;

}

printf("%d\n", ans);

for(int i = 1; i <= n; i++)

if(getfa(i) == i)

printf("%d ", i);

puts("");

}

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, k, ans;
int fa[50005], w[50005];
int getfa(int x)
{
    if(x == fa[x])return x;
    int t = fa[x]; fa[x] = getfa(fa[x]);
    w[x] = (w[x] + w[t]) % 3;
    return fa[x];
}
int main()
{
    n = read(); k = read();
    for(int i = 1; i <= n; i++)
        fa[i] = i;        
    for(int i = 1; i <= k; i++)
    {
        int d = read(), x = read(), y = read();
        if(x > n || y > n || (x == y && d == 2))
            ans++;
        else
        {
            int fx = getfa(x), fy = getfa(y);
            if(fx == fy)
            {
                if(d == 1 && w[x] != w[y])ans++;
                else if(d == 2 && (w[x] + 1) % 3 != w[y])ans++;
            }
            else
            {
                fa[fy] = fx;
                w[fy] = (d - 1 + w[x] - w[y] + 3) % 3;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n, k, ans;

int fa[50005], w[50005];

int getfa(int x)

{

if(x == fa[x])return x;

int t = fa[x]; fa[x] = getfa(fa[x]);

w[x] = (w[x] + w[t]) % 3;

return fa[x];

}

int main()

{

n = read(); k = read();

for(int i = 1; i <= n; i++)

fa[i] = i;

for(int i = 1; i <= k; i++)

{

int d = read(), x = read(), y = read();

if(x > n || y > n || (x == y && d == 2))

ans++;

else

{

int fx = getfa(x), fy = getfa(y);

if(fx == fy)

{

if(d == 1 && w[x] != w[y])ans++;

else if(d == 2 && (w[x] + 1) % 3 != w[y])ans++;

}

else

{

fa[fy] = fx;

w[fy] = (d - 1 + w[x] - w[y] + 3) % 3;

}

printf("%d\n", ans);

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T, n, m;
int fa[4005];
int getfa(int x)
{
    return x == fa[x]? x: fa[x] = getfa(fa[x]);
}
int main()
{
    T = read();
    for(int t = 1; t <= T; t++)
    {
        if(t != 1)
            puts("");
        printf("Scenario #%d:\n", t);
        n = read(); m = read();
        for(int i = 1; i <= 2 * n; i++)
            fa[i] = i;
        for(int i = 1; i <= m; i++)
        {
            int x = read(), y = read();
            fa[getfa(x)] = getfa(y + n);
            fa[getfa(y)] = getfa(x + n);
        }
        bool flag = 1;
        for(int i = 1; i <= n; i++)
            if(getfa(i) == getfa(i + n))
                flag = 0;
        if(flag)
            puts("No suspicious bugs found!");
        else
            puts("Suspicious bugs found!");
    }
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int T, n, m;

int fa[4005];

int getfa(int x)

{

return x == fa[x]? x: fa[x] = getfa(fa[x]);

}

int main()

{

T = read();

for(int t = 1; t <= T; t++)

{

if(t != 1)

puts("");

printf("Scenario #%d:\n", t);

n = read(); m = read();

for(int i = 1; i <= 2 * n; i++)

fa[i] = i;

for(int i = 1; i <= m; i++)

{

int x = read(), y = read();

fa[getfa(x)] = getfa(y + n);

fa[getfa(y)] = getfa(x + n);

}

bool flag = 1;

for(int i = 1; i <= n; i++)

if(getfa(i) == getfa(i + n))

flag = 0;

if(flag)

puts("No suspicious bugs found!");

else

puts("Suspicious bugs found!");

}

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m, cnt;
vector<int> e[100005];
int mx[100005], t[100005], exist[100005], id[100005];
void dfs(int x)
{
    id[x] = ++cnt;
    mx[x] = id[x];
    for(int i = 0; i < e[x].size(); i++)
    {
        if(mx[e[x][i]])continue;
        dfs(e[x][i]);
        mx[x] = max(mx[x], mx[e[x][i]]);
    }
}
void add(int x, int y)
{
    for(int i = x; i <= n; i += i & -i)
        t[i] += y;
}
int query(int x)
{
    int sum = 0;
    for(int i = x; i; i -= i & -i)
        sum += t[i];
    return sum;
}
int main()
{
    n = read();
    for(int i = 1; i < n; i++)
    {
        int x = read(), y = read();
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1);
    for(int i = 1; i <= n; i++)
    {
        add(i, 1);
        exist[i] = 1;
    }
    m = read();
    while(m--)
    {
        char ch[2];
        scanf("%s", ch);
        int x = read();
        if(ch[0] == 'Q')
            printf("%d\n", query(mx[x]) - query(id[x] - 1));
        else
        {
            if(exist[x])
                add(id[x], -1);
            else
                add(id[x], 1);
            exist[x] ^= 1;
        }
    }
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n, m, cnt;

vector<int> e[100005];

int mx[100005], t[100005], exist[100005], id[100005];

void dfs(int x)

{

id[x] = ++cnt;

mx[x] = id[x];

for(int i = 0; i < e[x].size(); i++)

{

if(mx[e[x][i]])continue;

dfs(e[x][i]);

mx[x] = max(mx[x], mx[e[x][i]]);

}

void add(int x, int y)

{

for(int i = x; i <= n; i += i & -i)

t[i] += y;

}

int query(int x)

{

int sum = 0;

for(int i = x; i; i -= i & -i)

sum += t[i];

return sum;

}

int main()

{

n = read();

for(int i = 1; i < n; i++)

{

int x = read(), y = read();

e[x].push_back(y);

e[y].push_back(x);

}

dfs(1);

for(int i = 1; i <= n; i++)

{

add(i, 1);

exist[i] = 1;

}

m = read();

while(m--)

{

char ch[2];

scanf("%s", ch);

int x = read();

if(ch[0] == 'Q')

printf("%d\n", query(mx[x]) - query(id[x] - 1));

else

{

if(exist[x])

add(id[x], -1);

else

add(id[x], 1);

exist[x] ^= 1;

}

return 0;

}

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long
#define pa pair<int,int>
#define mod 10007
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int t[2005][2005];
void add(int x, int y, int v)
{
	for(int i = x; i <= n; i += i & -i)
		for(int j = y; j <= n; j += j & -j)
			t[i][j] += v;
}
int query(int x, int y)
{
	int ans = 0;
	for(int i = x; i; i -= i & -i)
		for(int j = y; j; j -= j & -j)
			ans += t[i][j];
	return ans;
}
int main()
{
	int opt, x, y, l, r, v;
	opt = read(); n = read();
	memset(t, 0, sizeof(t));
	while(1)
	{
		opt = read();
		if(opt == 3)break;
		if(opt == 1)
		{
			x = read(), y = read(), v = read();
			add(x + 1, y + 1, v);
		}
		else
		{
			x = read(), y = read(), l = read(), r = read();
			printf("%d\n", query(l + 1, r + 1) - query(l + 1, y) - query(x, r + 1) + query(x, y));
		}
	}
	return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

#include<map>

#include<set>

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

#define pa pair<int,int>

#define mod 10007

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

int t[2005][2005];

void add(int x, int y, int v)

{

for(int i = x; i <= n; i += i & -i)

for(int j = y; j <= n; j += j & -j)

t[i][j] += v;

}

int query(int x, int y)

{

int ans = 0;

for(int i = x; i; i -= i & -i)

for(int j = y; j; j -= j & -j)

ans += t[i][j];

return ans;

}

int main()

{

int opt, x, y, l, r, v;

opt = read(); n = read();

memset(t, 0, sizeof(t));

while(1)

{

opt = read();

if(opt == 3)break;

if(opt == 1)

{

x = read(), y = read(), v = read();

add(x + 1, y + 1, v);

}

else

{

x = read(), y = read(), l = read(), r = read();

printf("%d\n", query(l + 1, r + 1) - query(l + 1, y) - query(x, r + 1) + query(x, y));

}

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int a[300005], last[300005];
int main()
{
    n = read();
    for(int i = 1; i <= n; i++)
        a[i] = read();
    int ans = 0;
    memset(last, 127, sizeof(last));
    last[0] = 0;    
    for(int i = 1; i <= n; i++)
    {
        int t = upper_bound(last + 1, last + n + 1, a[i]) - last;
        last[t] = min(last[t], a[i]);
        ans = max(ans, t);
    }
    printf("%d\n", ans);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

int a[300005], last[300005];

int main()

{

n = read();

for(int i = 1; i <= n; i++)

a[i] = read();

int ans = 0;

memset(last, 127, sizeof(last));

last[0] = 0;

for(int i = 1; i <= n; i++)

{

int t = upper_bound(last + 1, last + n + 1, a[i]) - last;

last[t] = min(last[t], a[i]);

ans = max(ans, t);

}

printf("%d\n", ans);

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
#define mod 1000000007
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int a[100005];
int sum[400005], ans[100005], tl[400005], tr[400005];
void build(int k, int l, int r)
{
    tl[k] = l; tr[k] = r;
    if(l == r)
    {
        sum[k] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    sum[k] = sum[k << 1] + sum[k << 1 | 1];
}
void del(int k, int x)
{
    int l = tl[k], r = tr[k], mid = (l + r) >> 1;
    if(l == r)
    {
        sum[k] = 0;
        return;        
    }    
    if(x <= mid)del(k << 1, x);
    else del(k << 1 | 1, x);
    sum[k] = sum[k << 1] + sum[k << 1 | 1];
}
int query(int k, int x)
{   
    int l = tl[k], r = tr[k], mid = (l + r) >> 1;
    if(l == r)
        return l;
    if(sum[k << 1] < x)
        return query(k << 1 | 1, x - sum[k << 1]);
    else return query(k << 1, x);
}
int main()
{
    n = read();
    for(int i = 2; i <= n; i++)
        a[i] = read();
    build(1, 1, n);
    for(int i = n; i >= 1; i--)
    {
        ans[i] = query(1, a[i] + 1);
        del(1, ans[i]);
    }
    for(int i = 1; i <= n; i++)
        printf("%d\n", ans[i]);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

#define mod 1000000007

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n;

int a[100005];

int sum[400005], ans[100005], tl[400005], tr[400005];

void build(int k, int l, int r)

{

tl[k] = l; tr[k] = r;

if(l == r)

{

sum[k] = 1;

return;

}

int mid = (l + r) >> 1;

build(k << 1, l, mid);

build(k << 1 | 1, mid + 1, r);

sum[k] = sum[k << 1] + sum[k << 1 | 1];

}

void del(int k, int x)

{

int l = tl[k], r = tr[k], mid = (l + r) >> 1;

if(l == r)

{

sum[k] = 0;

return;

}

if(x <= mid)del(k << 1, x);

else del(k << 1 | 1, x);

sum[k] = sum[k << 1] + sum[k << 1 | 1];

}

int query(int k, int x)

{

int l = tl[k], r = tr[k], mid = (l + r) >> 1;

if(l == r)

return l;

if(sum[k << 1] < x)

return query(k << 1 | 1, x - sum[k << 1]);

else return query(k << 1, x);

}

int main()

{

n = read();

for(int i = 2; i <= n; i++)

a[i] = read();

build(1, 1, n);

for(int i = n; i >= 1; i--)

{

ans[i] = query(1, a[i] + 1);

del(1, ans[i]);

}

for(int i = 1; i <= n; i++)

printf("%d\n", ans[i]);

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int T, n, ans;
int x[10005], y[10005], a[20005], vis[10005];
int l[100005], r[100005], c[100005];
void build(int k, int x, int y)
{
    int mid = (x + y) >> 1;    
    c[k] = 0; l[k] = x; r[k] = y;
    if(x == y)return;
    build(k << 1, x, mid);
    build(k << 1 | 1, mid + 1, y);
}
void modify(int k, int x, int y, int v)
{
    int L = l[k], R = r[k], mid = (L + R) >> 1;
    if(c[k] && L != R)
    {
        c[k << 1] = c[k];
        c[k << 1 | 1] = c[k];
        c[k] = 0;
    }
    if(L == x && y == R)
    {
        c[k] = v;
        return;
    }
    if(x <= mid)
        modify(k << 1, x, min(mid, y), v);
    if(y > mid)
        modify(k << 1 | 1, max(x, mid + 1), y, v);
}
int query(int k, int x)
{
    int L = l[k], R = r[k], mid = (L + R) >> 1;
    if(c[k] || L == R)
        return c[k];
    if(x <= mid)
        return query(k << 1, x);
    else return query(k << 1 | 1, x);
}
void dfs(int k)
{
    if(c[k])
    {
        if(!vis[c[k]])
        {
            ans++;
            vis[c[k]] = 1;
        }
        return;
    }
    if(l[k] == r[k])return;
    dfs(k << 1);
    dfs(k << 1 | 1);
}
int main()  
{
    T = read();
    while(T--)        
    {
        n = read();
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= n; i++)
        {
            x[i] = read(), y[i] = read();
            a[2 * i] = x[i];
            a[2 * i - 1] = y[i];
        }
        sort(a + 1, a + 2 * n + 1);
        for(int i = 1; i <= n; i++)
        {
            x[i] = lower_bound(a + 1, a + 2 * n + 1, x[i]) - a;
            y[i] = lower_bound(a + 1, a + 2 * n + 1, y[i]) - a;
        }
        build(1, 1, 2 * n);
        for(int i = 1; i <= n; i++)
            modify(1, x[i], y[i], i);
        ans = 0;
        dfs(1);
        cout << ans << endl;
    }
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int T, n, ans;

int x[10005], y[10005], a[20005], vis[10005];

int l[100005], r[100005], c[100005];

void build(int k, int x, int y)

{

int mid = (x + y) >> 1;

c[k] = 0; l[k] = x; r[k] = y;

if(x == y)return;

build(k << 1, x, mid);

build(k << 1 | 1, mid + 1, y);

}

void modify(int k, int x, int y, int v)

{

int L = l[k], R = r[k], mid = (L + R) >> 1;

if(c[k] && L != R)

{

c[k << 1] = c[k];

c[k << 1 | 1] = c[k];

c[k] = 0;

}

if(L == x && y == R)

{

c[k] = v;

return;

}

if(x <= mid)

modify(k << 1, x, min(mid, y), v);

if(y > mid)

modify(k << 1 | 1, max(x, mid + 1), y, v);

}

int query(int k, int x)

{

int L = l[k], R = r[k], mid = (L + R) >> 1;

if(c[k] || L == R)

return c[k];

if(x <= mid)

return query(k << 1, x);

else return query(k << 1 | 1, x);

}

void dfs(int k)

{

if(c[k])

{

if(!vis[c[k]])

{

ans++;

vis[c[k]] = 1;

}

return;

}

if(l[k] == r[k])return;

dfs(k << 1);

dfs(k << 1 | 1);

}

int main()

{

T = read();

while(T--)

{

n = read();

memset(vis, 0, sizeof(vis));

for(int i = 1; i <= n; i++)

{

x[i] = read(), y[i] = read();

a[2 * i] = x[i];

a[2 * i - 1] = y[i];

}

sort(a + 1, a + 2 * n + 1);

for(int i = 1; i <= n; i++)

{

x[i] = lower_bound(a + 1, a + 2 * n + 1, x[i]) - a;

y[i] = lower_bound(a + 1, a + 2 * n + 1, y[i]) - a;

}

build(1, 1, 2 * n);

for(int i = 1; i <= n; i++)

modify(1, x[i], y[i], i);

ans = 0;

dfs(1);

cout << ans << endl;

}

return 0;

}

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,sz,tot;
int root[100001],a[100001],ls[8000001],rs[8000001],s[8000001];
int num[100001],H[100001];
int find(int x)
{
    int l=1,r=tot,mid;
    while(l<=r)
    {
         int mid=(l+r)>>1;
         if(H[mid]<x)l=mid+1;
         else r=mid-1;
        } 
    return l;
}
void insert(int l,int r,int x,int &y,int v)
{
	y=++sz;
	s[y]=s[x]+1;
	if(l==r)return;
	ls[y]=ls[x];rs[y]=rs[x];
	int mid=(l+r)>>1;
	if(v<=mid)insert(l,mid,ls[x],ls[y],v);
	else insert(mid+1,r,rs[x],rs[y],v);
}
int ask(int l,int r,int x,int y,int k)
{
	if(l==r)return l;
	int mid=(l+r)>>1;
	if(s[ls[y]]-s[ls[x]]>=k)
	   return ask(l,mid,ls[x],ls[y],k);
	else return ask(mid+1,r,rs[x],rs[y],k-(s[ls[y]]-s[ls[x]]));
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
	   scanf("%d",&a[i]);
	   num[i]=a[i];
    }
    sort(num+1,num+n+1);
    H[++tot]=num[1];
    for(int i=2;i<=n;i++)
	   if(num[i]!=num[i-1])
	      H[++tot]=num[i];
	for(int i=1;i<=n;i++)
		insert(1,tot,root[i-1],root[i],find(a[i])); 
	for(int i=1;i<=m;i++)
	{
		int l,r,x;scanf("%d%d%d",&l,&r,&x);
		printf("%d\n",H[ask(1,tot,root[l-1],root[r],x)]);
	}
	return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int n,m,sz,tot;

int root[100001],a[100001],ls[8000001],rs[8000001],s[8000001];

int num[100001],H[100001];

int find(int x)

{

int l=1,r=tot,mid;

while(l<=r)

{

int mid=(l+r)>>1;

if(H[mid]<x)l=mid+1;

else r=mid-1;

}

return l;

}

void insert(int l,int r,int x,int &y,int v)

{

y=++sz;

s[y]=s[x]+1;

if(l==r)return;

ls[y]=ls[x];rs[y]=rs[x];

int mid=(l+r)>>1;

if(v<=mid)insert(l,mid,ls[x],ls[y],v);

else insert(mid+1,r,rs[x],rs[y],v);

}

int ask(int l,int r,int x,int y,int k)

{

if(l==r)return l;

int mid=(l+r)>>1;

if(s[ls[y]]-s[ls[x]]>=k)

return ask(l,mid,ls[x],ls[y],k);

else return ask(mid+1,r,rs[x],rs[y],k-(s[ls[y]]-s[ls[x]]));

}

int main()

{

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)

{

scanf("%d",&a[i]);

num[i]=a[i];

}

sort(num+1,num+n+1);

H[++tot]=num[1];

for(int i=2;i<=n;i++)

if(num[i]!=num[i-1])

H[++tot]=num[i];

for(int i=1;i<=n;i++)

insert(1,tot,root[i-1],root[i],find(a[i]));

for(int i=1;i<=m;i++)

{

int l,r,x;scanf("%d%d%d",&l,&r,&x);

printf("%d\n",H[ask(1,tot,root[l-1],root[r],x)]);

}

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m, ans;
int h[10005];
int cnt[40005], sum[40005], flag[40005];
int pl[40005], pr[40005];
struct rec{
    int x1, x2, y1, y2;    
}a[5005];
struct line{
    int x, v;
    int y1, y2;
}b[10005];
bool cmp(line a, line b)
{
    if(a.x != b.x)
        return a.x < b.x;
    return a.v > b.v;
}
void update(int k, int l, int r)
{
    if(flag[k])
    {
        sum[k] = h[r + 1] - h[l];
        cnt[k] = 1;
        pl[k] = pr[k] = 1;
    }
    else if(l != r)
    {
        sum[k] = sum[k << 1] + sum[k << 1 | 1];
        cnt[k] = cnt[k << 1] + cnt[k << 1 | 1] - (pr[k << 1] && pl[k << 1 | 1]);
        pl[k] = pl[k << 1];
        pr[k] = pr[k << 1 | 1];
    }
    else
        sum[k] = cnt[k] = pl[k] = pr[k] = 0;
}
void modify(int k, int L, int R, int l, int r, int v)
{
    if(L <= l && r <= R)
    {
        flag[k] += v;
        update(k, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    if(L <= mid)
        modify(k << 1, L, R, l, mid, v);
    if(mid < R)
        modify(k << 1 | 1, L, R, mid + 1, r, v);
    update(k, l, r);
}
int main()
{
    n = read();
    for(int i = 1; i <= n; i++)
    {
        a[i].x1 = read(), a[i].y1 = read(), a[i].x2 = read(), a[i].y2 = read();
        b[++m].x = a[i].x1; b[m].v = 1;
        b[++m].x = a[i].x2; b[m].v = -1;
        b[m].y1 = b[m - 1].y1 = a[i].y1;
        b[m].y2 = b[m - 1].y2 = a[i].y2;
        h[m] = a[i].y1;
        h[m - 1] = a[i].y2;
    }
    sort(b + 1, b + m + 1, cmp);
    sort(h + 1, h + m + 1);
    int L, R, last = 0;
    for(int i = 1; i <= m; i++)
    {
        ans += (b[i].x - b[i - 1].x) * cnt[1] * 2;
        L = lower_bound(h + 1, h + m + 1, b[i].y1) - h;
        R = lower_bound(h + 1, h + m + 1, b[i].y2) - h - 1;
        modify(1, L, R, 1, m, b[i].v);
        ans += abs(sum[1] - last);
        last = sum[1];
    }
    cout << ans << endl;
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n, m, ans;

int h[10005];

int cnt[40005], sum[40005], flag[40005];

int pl[40005], pr[40005];

struct rec{

int x1, x2, y1, y2;

}a[5005];

struct line{

int x, v;

int y1, y2;

}b[10005];

bool cmp(line a, line b)

{

if(a.x != b.x)

return a.x < b.x;

return a.v > b.v;

}

void update(int k, int l, int r)

{

if(flag[k])

{

sum[k] = h[r + 1] - h[l];

cnt[k] = 1;

pl[k] = pr[k] = 1;

}

else if(l != r)

{

sum[k] = sum[k << 1] + sum[k << 1 | 1];

cnt[k] = cnt[k << 1] + cnt[k << 1 | 1] - (pr[k << 1] && pl[k << 1 | 1]);

pl[k] = pl[k << 1];

pr[k] = pr[k << 1 | 1];

}

else

sum[k] = cnt[k] = pl[k] = pr[k] = 0;

}

void modify(int k, int L, int R, int l, int r, int v)

{

if(L <= l && r <= R)

{

flag[k] += v;

update(k, l, r);

return;

}

int mid = (l + r) >> 1;

if(L <= mid)

modify(k << 1, L, R, l, mid, v);

if(mid < R)

modify(k << 1 | 1, L, R, mid + 1, r, v);

update(k, l, r);

}

int main()

{

n = read();

for(int i = 1; i <= n; i++)

{

a[i].x1 = read(), a[i].y1 = read(), a[i].x2 = read(), a[i].y2 = read();

b[++m].x = a[i].x1; b[m].v = 1;

b[++m].x = a[i].x2; b[m].v = -1;

b[m].y1 = b[m - 1].y1 = a[i].y1;

b[m].y2 = b[m - 1].y2 = a[i].y2;

h[m] = a[i].y1;

h[m - 1] = a[i].y2;

}

sort(b + 1, b + m + 1, cmp);

sort(h + 1, h + m + 1);

int L, R, last = 0;

for(int i = 1; i <= m; i++)

{

ans += (b[i].x - b[i - 1].x) * cnt[1] * 2;

L = lower_bound(h + 1, h + m + 1, b[i].y1) - h;

R = lower_bound(h + 1, h + m + 1, b[i].y2) - h - 1;

modify(1, L, R, 1, m, b[i].v);

ans += abs(sum[1] - last);

last = sum[1];

}

cout << ans << endl;

return 0;

}

hzwer.com _ Home | http://hzwer.com

分类目录

热门文章

Myfriends

近期评论